HomeSubjectsUniversityBlogAbout

Tree Algorithms

Topic in Data Structures & Algorithms

210 total MCQsShowing 30 with explanations10 Easy10 Medium10 Hard
Start Timed Quiz on Tree AlgorithmsBack to Data Structures & Algorithms

About This Topic

Tree algorithms are procedures for traversing, searching, inserting into, deleting from and balancing hierarchical structures such as binary search trees. Traversal questions test pre-order, in-order, post-order and level-order visits, noting that in-order on a BST gives sorted output and level-order uses a queue. BST deletion of a node with two children, replacing it with its in-order successor or predecessor, is a favourite. Balanced trees feature heavily: AVL rotations and balance factors, Red-Black tree colouring rules with O(log n) insertion, and B-trees for disk-based indexing. Segment trees for range queries, height computation and space-saving Morris traversal also come up.

Below are 30 practice questions from a pool of 210 Tree Algorithms MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.

Practice Questions

Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.

Tree AlgorithmsEasy

Q1. How do you find the minimum element in a BST?

  1. A.Check the root node
  2. B.Traverse to the rightmost node
  3. C.Perform in-order traversal
  4. D.Traverse to the leftmost node✓ Correct

Explanation

In a BST, the minimum element is at the leftmost node, found by following left child pointers from the root.

Report an error in this question

Tree AlgorithmsEasy

Q2. Which traversal of a BST gives elements in sorted order?

  1. A.Level-order
  2. B.In-order✓ Correct
  3. C.Post-order
  4. D.Pre-order

Explanation

In-order traversal of a BST visits nodes in ascending sorted order (left, root, right).

Report an error in this question

Tree AlgorithmsEasy

Q3. What data structure is used for level-order (BFS) traversal of a tree?

  1. A.Array
  2. B.Queue✓ Correct
  3. C.Hash table
  4. D.Stack

Explanation

Level-order traversal uses a queue to process nodes level by level, enqueueing children as each node is visited.

Report an error in this question

Tree AlgorithmsEasy

Q4. What is post-order traversal of a binary tree?

  1. A.Right, Root, Left
  2. B.Root, Left, Right
  3. C.Left, Root, Right
  4. D.Left, Right, Root✓ Correct

Explanation

Post-order traversal visits the left subtree, then the right subtree, then the root (Left, Right, Root).

Report an error in this question

Tree AlgorithmsEasy

Q5. What is the height of a single-node tree?

  1. A.1
  2. B.0✓ Correct
  3. C.-1
  4. D.2

Explanation

A tree with a single node (root only) has height 0, as there are no edges from the root to any leaf.

Report an error in this question

Tree AlgorithmsEasy

Q6. How do you find the maximum element in a BST?

  1. A.Check the root node
  2. B.Traverse to the leftmost node
  3. C.Traverse to the rightmost node✓ Correct
  4. D.Use binary search method

Explanation

In a BST, the maximum element is at the rightmost node, found by following right child pointers from the root.

Report an error in this question

Tree AlgorithmsEasy

Q7. What is a binary tree's depth?

  1. A.The edge count from root to deepest leaf✓ Correct
  2. B.The total number of nodes in tree
  3. C.The number of internal non-leaf nodes
  4. D.The total number of leaf nodes only

Explanation

The depth (or height) of a binary tree is the number of edges on the longest path from the root to a leaf node.

Report an error in this question

Tree AlgorithmsMedium

Q8. What is an AVL tree?

  1. A.A tree with at most 3 children per node always
  2. B.A self-balancing BST with height difference at most 1✓ Correct
  3. C.A tree data structure used only for searching
  4. D.A binary tree with no balancing guarantees

Explanation

An AVL tree is a self-balancing BST where for every node, the heights of the left and right subtrees differ by at most 1.

Report an error in this question

Tree AlgorithmsEasy

Q9. What is the time complexity of searching for an element in a BST of height h?

  1. A.O(1)
  2. B.O(n^2)
  3. C.O(h)✓ Correct
  4. D.O(n)

Explanation

Search in a BST follows a path from root to a node, taking O(h) time where h is the height of the tree.

Report an error in this question

Tree AlgorithmsMedium

Q10. What are the rotation operations in an AVL tree?

  1. A.Merge and split operations on subtrees
  2. B.Insert and delete operations on tree nodes
  3. C.Push and pop operations on internal nodes
  4. D.Left, right, left-right, and right-left rotations✓ Correct

Explanation

AVL trees use four types of rotations to maintain balance: single left, single right, left-right (double), and right-left (double) rotations.

Report an error in this question

Tree AlgorithmsEasy

Q11. What is in-order traversal of a binary tree?

  1. A.Right, Root, Left
  2. B.Left, Right, Root
  3. C.Left, Root, Right✓ Correct
  4. D.Root, Left, Right

Explanation

In-order traversal visits the left subtree first, then the root, then the right subtree (Left, Root, Right).

Report an error in this question

Tree AlgorithmsEasy

Q12. What is pre-order traversal of a binary tree?

  1. A.Right, Left, Root
  2. B.Root, Left, Right✓ Correct
  3. C.Left, Right, Root
  4. D.Left, Root, Right

Explanation

Pre-order traversal visits the root first, then the left subtree, then the right subtree (Root, Left, Right).

Report an error in this question

Tree AlgorithmsHard

Q13. What is a Fenwick tree (Binary Indexed Tree)?

  1. A.A balanced BST variant with extra pointers
  2. B.A structure for O(log n) prefix sums and updates✓ Correct
  3. C.A tree used in networking protocols
  4. D.A binary tree indexed by key values

Explanation

A Fenwick tree (BIT) provides O(log n) time for both prefix sum queries and point updates, using a compact array-based representation.

Report an error in this question

Tree AlgorithmsMedium

Q14. What properties must a Red-Black tree satisfy?

  1. A.All internal and external nodes must always be colored red only
  2. B.Root is black, red nodes have black children, equal black-height on all paths✓ Correct
  3. C.Height is always kept at exactly log n for any n total nodes
  4. D.All leaf nodes are always colored red throughout the entire tree

Explanation

Red-Black tree properties: (1) every node is red or black, (2) root is black, (3) leaves (NIL) are black, (4) red nodes have black children, (5) all root-to-leaf paths have the same number of black nodes.

Report an error in this question

Tree AlgorithmsMedium

Q15. How can you check if a binary tree is a valid BST?

  1. A.Check if each node has at most 2 children
  2. B.Count the number of nodes in the tree
  3. C.Verify in-order traversal is strictly increasing✓ Correct
  4. D.Check if the root is the minimum value node

Explanation

A valid BST produces a strictly increasing sequence during in-order traversal. Alternatively, recursively check that each node's value is within a valid range.

Report an error in this question

Tree AlgorithmsMedium

Q16. What is a segment tree used for?

  1. A.Storing sorted segments of linked lists
  2. B.Efficient range queries and point updates on arrays✓ Correct
  3. C.Segmenting a network into subnetworks
  4. D.Storing geometric line segments only

Explanation

A segment tree is used for efficient range queries (e.g., sum, minimum, maximum) and updates on an array, both in O(log n) time.

Report an error in this question

Tree AlgorithmsMedium

Q17. When is a left rotation performed in an AVL tree?

  1. A.When the tree is already perfectly balanced
  2. B.When the right subtree is too heavy (RR case)✓ Correct
  3. C.When the left subtree is too heavy overall
  4. D.After every single insertion operation occurs

Explanation

A left rotation is performed when the right subtree is heavier (right-right imbalance) to restore the AVL balance property.

Report an error in this question

Tree AlgorithmsHard

Q18. What is a treap?

  1. A.A BST-heap hybrid with keys and random priorities✓ Correct
  2. B.A tree-shaped trap data structure
  3. C.A triple-ended queue data structure
  4. D.A tree with array-like access properties

Explanation

A treap is a randomized BST where each node has a key (BST property) and a random priority (heap property), providing O(log n) expected time for operations.

Report an error in this question

Tree AlgorithmsHard

Q19. What is the time complexity of range query and update in a segment tree?

  1. A.O(n) for both operations
  2. B.O(n) query, O(1) update
  3. C.O(1) query, O(n) update
  4. D.O(log n) for both operations✓ Correct

Explanation

A segment tree supports both range queries and point updates in O(log n) time.

Report an error in this question

Tree AlgorithmsHard

Q20. What is lazy propagation in a segment tree?

  1. A.Deferring updates to children until they are queried✓ Correct
  2. B.Lazily inserting elements one at a time
  3. C.Skipping unnecessary queries for performance
  4. D.Delaying the tree construction until needed

Explanation

Lazy propagation defers range updates to child nodes until those nodes are queried, enabling O(log n) range updates instead of O(n).

Report an error in this question

Tree AlgorithmsMedium

Q21. What is the time complexity of insertion in a Red-Black tree?

  1. A.O(1)
  2. B.O(n)
  3. C.O(n log n)
  4. D.O(log n)✓ Correct

Explanation

Red-Black tree insertion takes O(log n) time because the tree height is O(log n) and rebalancing (recoloring and rotations) takes O(log n) in the worst case.

Report an error in this question

Tree AlgorithmsMedium

Q22. What is the Lowest Common Ancestor (LCA) of two nodes in a tree?

  1. A.The deepest node that is ancestor of both✓ Correct
  2. B.The node with the smallest key value
  3. C.The root node of the entire tree
  4. D.The immediate parent of both given nodes

Explanation

The LCA of two nodes is the deepest (farthest from root) node that is an ancestor of both nodes.

Report an error in this question

Tree AlgorithmsMedium

Q23. What is Morris traversal?

  1. A.A traversal technique for graphs only
  2. B.An in-order traversal using O(1) extra space✓ Correct
  3. C.A traversal using an explicit stack structure
  4. D.A breadth-first traversal using a queue

Explanation

Morris traversal performs in-order traversal without a stack or recursion by using threaded binary tree concepts, temporarily modifying pointers and restoring them.

Report an error in this question

Tree AlgorithmsHard

Q24. What is a splay tree?

  1. A.A B-tree variant used in database indexing
  2. B.A self-adjusting BST that moves accessed nodes to root✓ Correct
  3. C.A tree that spreads elements across multiple arrays
  4. D.A tree that is always perfectly balanced

Explanation

A splay tree is a self-adjusting BST that performs a splay operation (sequence of rotations) to move an accessed node to the root, providing O(log n) amortized time.

Report an error in this question

Tree AlgorithmsMedium

Q25. How do you delete a node with two children in a BST?

  1. A.Simply remove the node directly from tree
  2. B.Swap with the root node then remove it
  3. C.Replace with in-order successor then delete it✓ Correct
  4. D.Set the node value to null and leave it

Explanation

To delete a node with two children, replace its value with its in-order successor (smallest in right subtree) or predecessor (largest in left subtree), then delete that successor/predecessor.

Report an error in this question

Tree AlgorithmsHard

Q26. What is the Euler tour technique for trees?

  1. A.Linearizing a tree by recording DFS visit times✓ Correct
  2. B.A graph coloring technique for tree nodes
  3. C.Touring all leaf nodes in level order
  4. D.Finding Euler paths in tree structures

Explanation

The Euler tour technique linearizes a tree into a sequence by recording entry and exit times during DFS, enabling subtree queries to be converted to range queries.

Report an error in this question

Tree AlgorithmsHard

Q27. What is Heavy-Light Decomposition (HLD) of a tree?

  1. A.Decomposing into chains for efficient path queries✓ Correct
  2. B.Separating heavy and light weight nodes
  3. C.Removing heavy edges from the tree structure
  4. D.Balancing an unbalanced tree by restructuring

Explanation

HLD decomposes a tree into heavy and light chains so that any root-to-leaf path crosses at most O(log n) chains, enabling efficient path queries with segment trees.

Report an error in this question

Tree AlgorithmsHard

Q28. What is a persistent segment tree?

  1. A.A segment tree preserving all versions via path copying✓ Correct
  2. B.A segment tree that never changes after construction
  3. C.A segment tree stored on disk permanently
  4. D.A compressed segment tree with reduced memory use

Explanation

A persistent segment tree creates a new version for each update by copying only the modified path (O(log n) nodes), preserving all historical versions.

Report an error in this question

Tree AlgorithmsHard

Q29. How does a B+ tree differ from a B-tree?

  1. A.B+ tree is not a balanced tree structure
  2. B.B+ tree has more levels than a B-tree
  3. C.B+ tree stores all data at leaves with linked leaf nodes✓ Correct
  4. D.B+ tree has fewer keys per node overall

Explanation

In a B+ tree, only leaf nodes store data records (internal nodes store only keys for routing), and leaf nodes are linked together, supporting efficient range queries.

Report an error in this question

Tree AlgorithmsHard

Q30. What is the time complexity of LCA using binary lifting (sparse table)?

  1. A.O(n^2) per query with no preprocessing needed
  2. B.O(n) per query with no preprocessing
  3. C.O(1) per query after O(n^2) preprocessing
  4. D.O(log n) per query after O(n log n) preprocessing✓ Correct

Explanation

Binary lifting preprocesses ancestor information in O(n log n) and answers each LCA query in O(log n) by jumping up in powers of 2.

Report an error in this question

More Data Structures & Algorithms Topics

Foundations of DS & Algorithms

Practice MCQs with explanations

Linear Data Structures

Practice MCQs with explanations

Non-Linear Data Structures

Practice MCQs with explanations

Searching Algorithms

Practice MCQs with explanations

Sorting Algorithms

Practice MCQs with explanations

Hashing

Practice MCQs with explanations

Ready to test yourself on Tree Algorithms?

Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.

Start Tree Algorithms Quiz