Traversals

ACompressed recap

🧾

The recursive traversals differ only in when the root is visited: preorder (root, L, R), inorder (L, root, R), postorder (L, R, root); an Euler walk gives all three. Level order uses a queue. Inorder plus pre-, post- or level order rebuilds a unique binary tree; pre + post does not (except for strict trees). There are C(n) binary tree shapes with n nodes, n!·C(n) labelled trees.

BMerged rule card

4.3.1 Preorder, inorder, postorder (recursive code and hand tracing)

• Preorder: root, L, R. Inorder: L, root, R. Postorder: L, R, root.
• Euler walk: 1st touch pre, 2nd in, 3rd post.
• O(n) time; depth = height + 1.
• Read mixed traversals statement by statement (before/between/after calls).

4.3.2 Level-order traversal using a queue

• Level order: enqueue root; repeat: dequeue, print, enqueue left then right.
• O(n) time; queue holds at most about one level (≤ n/2 for complete trees).
• Stack → branch-first; queue → level order.
• Separate levels by recording the queue size; height = levels − 1.
• Array without holes: level order = index order.

4.3.3 Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)

• Pre + in or post + in or level + in → unique tree; pre + post only for strict trees.
• Root: first of pre, last of post; inorder splits left/right.
• Shapes with n nodes: Catalan C(n) = (2n choose n)/(n + 1).
• Labelled binary trees: n!·C(n); trees with a fixed preorder: C(n).

CInterleaved GATE-style questions

Q1MCQ1 markInorder

Inorder of the Lesson 4.3.1 Example 1 tree:

• (A) A B D E G H C F I
• (B) A B C D E F G H I
• (C) D B G E H A C I F
• (D) D G H E B I F C A

Q2MCQ2 marksRebuild

Postorder D E B F C A and inorder D B E A F C. What is the preorder?

• (A) A B D E C F
• (B) A D B E C F
• (C) A B D E F C
• (D) A B C D E F

Q3NAT1 markCatalan

How many binary tree shapes have 6 nodes?

Numerical answer: ________

Q4MCQ1 markQueue

Which traversal needs a queue rather than recursion?

• (A) preorder
• (B) inorder
• (C) level order
• (D) postorder

Q5NAT2 marksOutput

How many numbers does this program print, counting duplicates?

void f(struct tnode *t)
{
    if (t == NULL) return;
    printf("%d ", t->data);
    f(t->right);
    printf("%d ", t->data);
    f(t->left);
}

int main(void)
{
    struct tnode *root = mk(1, mk(2, NULL, NULL), mk(3, mk(4, NULL, NULL), NULL));
    f(root);
    printf("\n");
    return 0;
}

Numerical answer: ________

Q6MSQ1 markFacts

Which are true?

• (A) Postorder’s first element is the root.
• (B) Preorder’s first element is the root.
• (C) Inorder alone determines the tree.
• (D) Level order’s first element is the root.

Q7MCQ2 marksTraversal

A tree has root * with left child + (whose children are a and b) and right child c. Its postorder is:

• (A) * + a b c
• (B) a b + c *
• (C) a + b * c
• (D) a b c + *

Q8NAT2 marksQueue size

During level order of a perfect binary tree of height 4, what is the largest number of nodes in the queue at once?

Numerical answer: ________

Q9MCQ1 markPre + post

Preorder 1 2 and postorder 2 1 fit how many binary trees?

• (A) 3
• (B) 0
• (C) 2
• (D) 1

DAnswer Vault