Trees, Traversals & Reconstruction

The last lesson left hashing fast but blind to order. The cure is to organise data not as a flat array of slots but as a branching hierarchy — and that shape is a tree. A tree is a set of nodes connected by parent-child edges, with one root at the top and no cycles. The natural question it raises is the one this lesson answers: in what order do you visit every node? That single question has four canonical answers, and GATE turns them into both straightforward 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 5

Now 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.

A question to carry forward

A tree is a strict hierarchy: one root, no cycles, every node with a single parent. That tidiness is exactly what made the traversals well-defined. But the real world is rarely so tidy — cities joined by many roads, web pages linking every which way, people tangled in a social network. These have no root, no notion of “parent,” and plenty of loops. Here is the thread onward: what happens when you drop the tree’s restrictions entirely and allow any nodes joined by any edges — how do you even represent such a tangle in memory, and what new vocabulary does it demand?

In one breath

• A tree: nodes with parent-child edges, one root, no cycles. Leaf = no children; height = longest root-to-leaf path (in edges).
• Binary tree = ≤ 2 children (left/right). Four traversals: preorder (root,L,R), inorder (L,root,R), postorder (L,R,root) — all DFS — and level-order (BFS, a queue).
• Root location: front of preorder, back of postorder; inorder gives the left/right split.
• Reconstruction: inorder + (pre OR post) ⇒ unique tree; pre + post alone is ambiguous for a general binary tree (GATE 2024).
• Bounds: height h ⇒ at most 2^(h+1) − 1 nodes; n nodes ⇒ height at least ⌊log₂ n⌋.

Practice