What this topic covers
17 subtopics- Traversals8
- Height and depth5
- Building trees4
- AVL trees3
- BST basics3
- BST search3
- Balanced trees2
- BST insertion2
- BST order statistics2
- Library trees2
- Range trees2
- Root-to-leaf paths2
Show all 17 subtopics
- Tree shapes2
- Tries2
- BST deletion1
- Lowest common ancestor1
- Tree transformations1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
Trees are drawn on this page, so you can read them the way you would on paper. Most tree questions are traversals: preorder (node, left, right), inorder (left, node, right – sorted for a BST), postorder (left, right, node) and level order (breadth-first). A binary search tree keeps smaller keys on the left and larger on the right, so search, insert and delete follow one path – O(h), which is O(log n) only when the tree is balanced. Every traversal and every tree in the answers was produced by a checker program.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
What is the inorder traversal of this tree?
Show answer and explanation
Explanation
Left subtree, node, right subtree – which for a BST lists the keys in sorted order.
Why the other options are wrong
- AThat is preorder.
- BThat is level order.
- DThat is postorder.
A binary tree has preorder 3 9 20 15 7 and inorder 9 3 15 20 7. What is its postorder?
Show answer and explanation
Explanation
Preorder's first value (3) is the root; in the inorder it splits left [9] from right [15, 20, 7]. The right part's preorder starts with 20, which splits 15 from 7. Postorder: 9, 15, 7, 20, 3.
Why the other options are wrong
- AThe left subtree comes before the right.
- BThat is the inorder given.
- D9, the whole left subtree, comes first.
Preorder 1 2 and postorder 2 1 describe a two-node tree. Why can the tree not be determined uniquely?
Show answer and explanation
Explanation
Both trees give the same pair of sequences. Inorder resolves it, because it tells which side of the root each key is on. GATE often asks which traversal pairs are sufficient.
Why the other options are wrong
- AThey are consistent with two different trees.
- BPostorder ends with the root.
- CNo such rule.