Binary Trees and Graphs Beginner Quiz
30 questions on Binary Trees & Graphs.
Question 1: What is a Binary Tree?
- A. A tree where every node has an infinite number of children
- B. A tree data structure in which each node has at most two children, referred to as the left child and the right child β (correct answer)
- C. A database table
- D. A graph with no edges
Explanation: Binary trees restrict each parent node to having exactly 0, 1, or 2 children, making algorithmic traversal structured and predictable.
Question 2: What is the "Root" of a tree?
- A. The bottom-most node
- B. The topmost node from which all other nodes descend β (correct answer)
- C. A node with exactly two children
- D. A node with no children
Explanation: Every tree has exactly one root node, which is the entry point for all traversal algorithms.
Question 3: What is a "Leaf" node?
- A. The root node
- B. A node with exactly one child
- C. A node that has no children β (correct answer)
- D. A node that points to itself
Explanation: Leaves are the terminal nodes at the bottom-most ends of the tree's branches.
Question 4: What defines a Binary Search Tree (BST)?
- A. All left descendants are smaller than the node, and all right descendants are greater than the node β (correct answer)
- B. Every node has exactly two children
- C. The tree is completely perfectly balanced
- D. The root node is always the minimum value
Explanation: This specific ordering makes BSTs incredibly efficient for searching, acting similar to a binary search on a sorted array.
Question 5: In a Binary Search Tree, what is the average time complexity for searching, inserting, and deleting a node?
- A. O(1)
- B. O(n)
- C. O(log n) β (correct answer)
- D. O(n^2)
Explanation: At each step, you eliminate half of the remaining tree (going left or right), resulting in logarithmic time complexity.
Question 6: Which tree traversal method visits the nodes in this exact order: Left Child -> Root -> Right Child?
- A. Preorder
- B. Inorder β (correct answer)
- C. Postorder
- D. Level Order
Explanation: In a Binary Search Tree, an Inorder traversal visits the nodes in ascending, sorted numerical order.
Question 7: Which tree traversal method visits the nodes in this exact order: Root -> Left Child -> Right Child?
- A. Preorder β (correct answer)
- B. Inorder
- C. Postorder
- D. Breadth-First
Explanation: Preorder traversal is commonly used to create a copy of the tree because it visits the parent node before its children.
Question 8: Which tree traversal method visits the nodes in this exact order: Left Child -> Right Child -> Root?
- A. Inorder
- B. Preorder
- C. Postorder β (correct answer)
- D. Deep-First
Explanation: Postorder is commonly used to delete the tree from memory because it safely deletes children before deleting the parent.
Question 9: What is the "Height" of a tree?
- A. The total number of nodes in the tree
- B. The number of edges on the longest path from the root node to a leaf β (correct answer)
- C. The sum of all node values
- D. The number of children the root has
Explanation: Height determines the worst-case time complexity for operations. A tree with a single node has a height of 0.
Question 10: What happens to the search time complexity of a BST if elements are inserted in already sorted order (e.g., 1, 2, 3, 4)?
- A. It remains O(log n)
- B. The tree automatically balances itself
- C. It degrades to O(n) because it essentially becomes a Linked List β (correct answer)
- D. The tree throws an error
Explanation: Without self-balancing algorithms (like AVL or Red-Black trees), consecutive ascending insertions all go to the right child, forming a straight line.
Question 11: What is a Graph in computer science?
- A. A visual chart (like a pie chart)
- B. A non-linear data structure consisting of Vertices (nodes) and Edges (links connecting the nodes) β (correct answer)
- C. A type of array
- D. A database schema
Explanation: Graphs are used to map relationships, such as computer networks, city maps, and social media friends.
Question 12: What is a "Directed Graph" (Digraph)?
- A. A graph where all edges have a specific direction (A -> B), like a one-way street β (correct answer)
- B. A graph with no edges
- C. A graph where edges go both ways automatically
- D. A graph strictly for numbers
Explanation: If node A has a directed edge to node B, you can travel from A to B, but not necessarily from B back to A.
Question 13: What is a "Weighted Graph"?
- A. A graph where nodes are physically heavy
- B. A graph where edges have numerical values (weights/costs) assigned to them, such as distance or time β (correct answer)
- C. A graph with many cycles
- D. A perfectly balanced graph
Explanation: Weighted graphs are used by GPS systems to calculate the fastest route, factoring in the "weight" (traffic time) of each street.
Question 14: What is the main difference between a Tree and a Graph?
- A. Trees have vertices, graphs do not
- B. Trees are a strict subset of graphs that must be connected and CANNOT contain cycles or loops β (correct answer)
- C. Graphs are used for sorting
- D. Trees are directed, graphs are undirected
Explanation: Every tree is technically a graph, but a graph is only a tree if it has a strict hierarchical structure with no circular paths.
Question 15: What is Breadth-First Search (BFS)?
- A. A graph traversal that dives as deep as possible before backtracking
- B. A graph traversal that explores all immediate neighbor nodes at the present depth before moving deeper β (correct answer)
- C. A sorting algorithm
- D. An algorithm for balancing trees
Explanation: BFS radiates outward layer by layer, making it the perfect algorithm for finding the shortest unweighted path between two nodes.
Question 16: Which core data structure is used behind the scenes to implement Breadth-First Search (BFS)?
- A. Stack
- B. Array
- C. Queue β (correct answer)
- D. Hash Table
Explanation: A Queue ensures First-In-First-Out (FIFO) processing, meaning neighbors discovered first are explored first.
Question 17: What is Depth-First Search (DFS)?
- A. Exploring layer by layer
- B. Exploring as far as possible along each branch before backtracking β (correct answer)
- C. Finding the shortest path
- D. Sorting edges by weight
Explanation: DFS is like solving a maze: you go down one path until you hit a dead end, then back up and try the next path.
Question 18: Which core data structure is used behind the scenes to implement Depth-First Search (DFS)?
- A. Stack (or the Call Stack via Recursion) β (correct answer)
- B. Queue
- C. Array
- D. Linked List
Explanation: A Stack ensures Last-In-First-Out (LIFO) processing, which naturally supports the "dive deep then backtrack" logic of DFS.
Question 19: When traversing a Graph (unlike a Tree), what must you track to prevent infinite loops?
- A. The depth of the tree
- B. A "Visited" set or array to keep track of nodes you have already processed β (correct answer)
- C. The number of edges
- D. The weights of the edges
Explanation: Because graphs can contain cycles (A -> B -> C -> A), failing to mark nodes as "visited" will cause your traversal algorithm to run infinitely in a loop.
Question 20: What is an "Adjacency List"?
- A. A mathematical formula
- B. A way to represent a graph where every vertex has a list of its directly connected neighbor vertices β (correct answer)
- C. A 2D array of all possible connections
- D. A list of edge weights
Explanation: Adjacency lists (e.g., A: [B, C]) are incredibly space-efficient for sparse graphs compared to Adjacency Matrices.
Question 21: What is an "Adjacency Matrix"?
- A. A list of neighbors
- B. A 2D array (V x V) where rows and columns represent vertices, and cells contain a 1 (or weight) if an edge exists between them β (correct answer)
- C. A balanced binary tree
- D. A database relationship
Explanation: Adjacency matrices provide O(1) edge lookup time but require O(V^2) memory space, making them bad for large graphs with few edges.
Question 22: What is Dijkstra's Algorithm?
- A. An algorithm to balance binary search trees
- B. A greedy algorithm that finds the shortest path from a starting node to all other nodes in a weighted graph (without negative weights) β (correct answer)
- C. An algorithm to sort graph vertices alphabetically
- D. A string search algorithm
Explanation: Dijkstra's continually explores the unvisited neighbor with the lowest total cumulative weight from the start node.
Question 23: What is a "Full Binary Tree"?
- A. A tree completely filled with data
- B. A binary tree in which every node has either 0 or 2 children (no node has exactly 1 child) β (correct answer)
- C. A completely balanced tree
- D. A tree that uses no memory
Explanation: In a full binary tree, branches always split into pairs, and no single-child nodes exist.
Question 24: What is a "Complete Binary Tree"?
- A. A tree where every level is completely filled, except possibly the last, which is filled from left to right β (correct answer)
- B. A tree with maximum depth
- C. A tree with no leaf nodes
- D. A tree sorted perfectly
Explanation: Complete binary trees are the structural foundation for "Heaps", allowing them to be efficiently stored in a flat array.
Question 25: What is a "Topological Sort"?
- A. Sorting graph nodes alphabetically
- B. A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge U -> V, vertex U comes before V β (correct answer)
- C. Sorting a binary tree
- D. A bubble sort for graphs
Explanation: Topological sorting is used to schedule tasks with dependencies (e.g., you cannot compile the main program until you compile the libraries).
Question 26: What is an "AVL Tree"?
- A. A graph traversal algorithm
- B. A self-balancing Binary Search Tree where the heights of the two child subtrees of any node differ by at most one β (correct answer)
- C. An unbalanced tree
- D. A tree with infinite children
Explanation: AVL trees automatically perform "rotations" during insertions to maintain balance, strictly guaranteeing O(log n) worst-case search time.
Question 27: In Dijkstra's algorithm, what data structure is used to efficiently fetch the unvisited node with the lowest current weight?
- A. Stack
- B. Hash Table
- C. Min-Priority Queue (Min-Heap) β (correct answer)
- D. Array
Explanation: Using a Min-Heap drops the time complexity from O(V^2) down to O(E log V) by instantly providing the minimum-weight node.
Question 28: What is a Directed Acyclic Graph (DAG)?
- A. A graph with no directions
- B. A directed graph that contains absolutely no cycles (no loops back to previous nodes) β (correct answer)
- C. A graph containing cyclic recursion
- D. A completely disconnected graph
Explanation: DAGs are required for Topological Sorts and represent systems like Git commits or software build pipelines where circular dependencies are illegal.
Question 29: What does the "A* (A-Star) Search Algorithm" do differently than Dijkstra's?
- A. It is slower than Dijkstra's
- B. It uses a "Heuristic" (an educated guess) to guide the search toward the destination, resulting in much faster pathfinding β (correct answer)
- C. It only works on unweighted graphs
- D. It randomly guesses the path
Explanation: While Dijkstra's blindly searches uniformly in all directions, A* uses distance estimates (like a straight-line bird's flight) to prioritize exploring paths moving closer to the target.
Question 30: What is "Kruskal's Algorithm" used for?
- A. Searching binary trees
- B. Finding the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph β (correct answer)
- C. Sorting edges
- D. Balancing a BST
Explanation: An MST connects all nodes in the graph using the absolute minimum total edge weight (e.g., laying down the least amount of copper wire to connect multiple houses).