Trees, Traversals & Reconstruction
How a binary tree is walked four canonical ways — pre, in, post, and level-order — and why inorder plus one other order rebuilds the tree but preorder + postorder does not.
What you'll learn
- Tree vocabulary: root, child, leaf, depth, height — and what a binary tree is
- Four traversals: preorder, inorder, postorder, and level-order (BFS)
- Reconstruction: inorder plus pre or post rebuilds a tree; pre + post alone does not
- Bounds: a height-h binary tree has at most 2^(h+1) − 1 nodes; n nodes need height at least floor(log2 n)
Before you start
A tree is a set of nodes connected by parent-child edges, with one root at the top and no cycles. The natural question is: in what order do you visit every node? That single question has four canonical answers, and GATE turns them into both traversal questions and the trickier reconstruction question — rebuilding a tree from its traversal sequences. The same traversals power real tools every day: a decision tree predicts by walking root-to-leaf, and parsers, file systems, and JSON walkers all lean on exactly these orders.
Vocabulary
A few terms you will see in every question:
- Root — the single top node, no parent.
- Child / parent — a node directly below / above another.
- Leaf — a node with no children.
- Depth of a node — edges from the root down to it (root has depth 0).
- Height of the tree — the longest root-to-leaf path, counted in edges.
A binary tree restricts every node to at most two children, the left and the right child. The order of left vs right matters — that is what makes the traversals below distinct.
The four traversals
Three of the four are depth-first (DFS) and differ only in when the root is visited relative to its subtrees. The fourth is breadth-first (BFS).
- Preorder — root, left, right (visit the root first).
- Inorder — left, root, right (root in the middle).
- Postorder — left, right, root (root last).
- Level-order (BFS) — top to bottom, left to right, one depth level at a time (driven by a queue, not recursion).
How GATE asks this
Two patterns. (1) Traversal: given a drawn tree, write a named order, or read a value off it (a NAT for “number of leaves” or “height”). (2) Reconstruction (asked 2024): given two traversal sequences, rebuild the tree or report a property of it — and the subtle point is which pair suffices. Inorder plus preorder (or inorder plus postorder) rebuilds a binary tree uniquely; preorder plus postorder alone does not.
Worked example
Take the tree above: root 1, with left child 2 (whose children are 4 and
5) and right child 3 (a leaf). Reading off each order:
Preorder (root, L, R): 1 2 4 5 3 → 1 2 4 5 3
Inorder (L, root, R): 4 2 5 1 3 → 4 2 5 1 3
Postorder (L, R, root): 4 5 2 3 1 → 4 5 2 3 1
Level-order (BFS): 1 | 2 3 | 4 5 → 1 2 3 4 5Now reconstruct from inorder + preorder — the 2024 question:
Preorder = 1 2 4 5 3 → first element 1 is the ROOT
Inorder = 4 2 5 1 3
↑ split inorder at 1:
left subtree = 4 2 5 right subtree = 3
Recurse on the left (preorder 2 4 5, inorder 4 2 5):
root = 2; inorder splits as 4 | 5 → children 4 (left) and 5 (right)
Right subtree is the single node 3.That rebuilds exactly the original tree — uniquely. The root always comes from the front of preorder (or the back of postorder), and inorder supplies the left/right split around it.
Quick bounds to memorise: a binary tree of height h has at most
2^(h+1) − 1 nodes (a full tree). Conversely, n nodes need height at least
floor(log2 n). Here n = 5, so the minimum possible height is
floor(log2 5) = 2 — and this tree achieves it.
Quick check
Quick check
Practice this in an interview
All questionsUse a queue (deque) to process nodes layer by layer. At each step, snapshot the current queue length to know exactly how many nodes belong to the current level, drain those, then enqueue their children. The result is a list of lists without any depth-tracking variable.
Iteratively: walk the list with three pointers — prev, current, and next — rewiring each node's pointer as you go. Recursively: reverse the rest of the list, then attach the current head to the new tail. Both are O(n) time, O(1) and O(n) space respectively.
The maximum depth is 1 plus the larger of the left and right subtree depths. A single recursive call naturally expresses this: at every node, ask both children for their depth and take the max. The base case is None, which returns 0.
At each step of a recursive walk through the input, you make a binary choice: include the current element or skip it. Recording the current path at every node of the recursion tree (not just the leaves) collects all 2^n subsets. A `start` index prevents duplicates by ensuring elements are only considered left-to-right.