Practice 20 Trees multiple-choice questions designed for CDAC CCAT exam preparation. Click "Show Answer" to reveal the correct option with detailed explanation.
Show Answer & Explanation
Correct Answer: C — 2^k
At level k (0-indexed), max nodes = 2^k. Level 0 has 1, level 1 has 2, etc.
Show Answer & Explanation
Correct Answer: B — n+1
A binary tree with n nodes has n+1 NULL pointers.
Show Answer & Explanation
Correct Answer: B — log n
Height of complete binary tree is O(log n).
Show Answer & Explanation
Correct Answer: B — Sorted order
Inorder traversal of BST gives elements in sorted (ascending) order.
Show Answer & Explanation
Correct Answer: C — O(log n) average
BST search is O(log n) on average, O(n) worst case (skewed tree).
Show Answer & Explanation
Correct Answer: B — Self-balancing BST
AVL tree is a self-balancing BST where height difference of subtrees ≤ 1.
Show Answer & Explanation
Correct Answer: B — Queue
Level order (BFS) traversal uses queue.
Show Answer & Explanation
Correct Answer: A — No parent
Root is the topmost node with no parent.
Show Answer & Explanation
Correct Answer: B — n-1
A tree with n nodes always has exactly n-1 edges.
Show Answer & Explanation
Correct Answer: B — Every node has 0 or 2 children
In full binary tree, every node has either 0 or 2 children.
Show Answer & Explanation
Correct Answer: B — All levels filled except possibly last, filled left to right
Complete binary tree has all levels filled except possibly the last, which is filled from left to right.
Show Answer & Explanation
Correct Answer: A — All internal nodes have 2 children and all leaves at same level
Perfect binary tree has all internal nodes with 2 children and all leaves at the same level.
Show Answer & Explanation
Correct Answer: B — Root, Left, Right
Preorder: Root first, then Left subtree, then Right subtree (Root-Left-Right).
Show Answer & Explanation
Correct Answer: C — Left, Right, Root
Postorder: Left subtree first, then Right subtree, then Root (Left-Right-Root).
Show Answer & Explanation
Correct Answer: C — floor(log2(n))
Minimum height is achieved in complete binary tree: floor(log2(n)).
Show Answer & Explanation
Correct Answer: B — O(log n) worst case operations
Red-Black tree is self-balancing, guaranteeing O(log n) for search, insert, delete.
Show Answer & Explanation
Correct Answer: B — Database indexing and file systems
B-trees are optimized for disk access and widely used in databases and file systems.
Show Answer & Explanation
Correct Answer: B — Deepest node that is ancestor of both
LCA is the deepest (lowest) node that has both given nodes as descendants.
Show Answer & Explanation
Correct Answer: C — Priority Queue
Binary heap efficiently implements priority queue with O(log n) insert and extract.
Show Answer & Explanation
Correct Answer: B — Inorder predecessor/successor
Threaded binary tree uses NULL pointers to store inorder predecessor or successor for efficient traversal.