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.

One of those definitions costs more marks than everything else on this page, so slow down on it: height is counted in edges here, not nodes. A tree consisting of one lonely node therefore has height 0, and the tree drawn below has height 2.

Plenty of textbooks count nodes instead, which would call those same two trees height 1 and height 3 — every answer shifted by one. Every formula in this lesson assumes the edge convention; when a paper is ambiguous, find out whether it calls a single node height 0 or height 1 and follow that.

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

Bounds

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.

Neither bound is worth memorising blind, because both fall out of one picture.

Each node has at most two children, so each level can at most double the one above it: level 0 holds at most 1 node, level 1 at most 2, level d at most 2^d. A tree of height h owns levels 0 through h, so it holds at most 1 + 2 + 4 + … + 2^h = 2^(h+1) − 1 nodes.

Read that backwards and the second bound appears: cram in more nodes and, since each level is capped, you are forced to add levels. A tree that hits the maximum — every level completely filled — is a perfect binary tree. (That is stricter than a full binary tree, which only demands that every internal node have exactly two children.)

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