Tree traversals (inorder, preorder, postorder) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Identify the traversal order

Given a binary tree, which traversal visits the root node first, then the left subtree, and finally the right subtree?

A Level-order traversal

B Inorder traversal

C Postorder traversal

D Preorder traversal

💡 Hint

Think about which traversal starts by visiting the root node before its children.

Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree.

📋 Factual

intermediate

Output of inorder traversal

What is the output sequence of an inorder traversal on the following binary tree?

2
/ \
1 3

A [2, 1, 3]

B [1, 2, 3]

C [3, 2, 1]

D [1, 3, 2]

💡 Hint

Inorder traversal visits left subtree, root, then right subtree.

Inorder traversal visits nodes in ascending order for a binary search tree: left child (1), root (2), right child (3).

🔍 Analysis

advanced

Determine postorder traversal output

Consider this binary tree:

A
/ \
B C
/ / \
D E F

What is the postorder traversal output?

A [B, D, A, E, F, C]

B [A, B, D, C, E, F]

C [D, B, E, F, C, A]

D [D, B, C, E, F, A]

💡 Hint

Postorder traversal visits left subtree, right subtree, then root.

Postorder visits D (leftmost), then B, then E and F (right subtree), then C, and finally root A.

❓ Comparison

advanced

Compare preorder and postorder traversals

Which statement correctly compares preorder and postorder traversals of a binary tree?

A Preorder visits the root before its subtrees; postorder visits the root after its subtrees.

B Preorder visits the root after its subtrees; postorder visits the root before its subtrees.

C Both preorder and postorder visit the root at the same time.

D Preorder and postorder always produce the same node sequence.

💡 Hint

Think about when the root node is visited in each traversal.

Preorder traversal visits the root node first, while postorder traversal visits it last after its children.

❓ Reasoning

expert

Number of nodes visited in preorder traversal

A binary tree has 7 nodes. How many nodes will be visited during a complete preorder traversal?

A 7

B 6

C 8

D Depends on the tree structure

💡 Hint

Traversal visits every node exactly once.

Preorder traversal visits every node in the tree exactly once, so all 7 nodes are visited.

Practice

1. Which tree traversal visits the root node first, then the left subtree, and finally the right subtree?

easy

A. Preorder traversal

B. Inorder traversal

C. Postorder traversal

D. Level order traversal

Solution

1. Step 1: Understand preorder traversal order

   Preorder traversal visits nodes in the order: root, left subtree, right subtree.

2. Step 2: Compare with other traversal types

   Inorder visits left, root, right; postorder visits left, right, root; level order visits level by level.

3. Final Answer:

   Preorder traversal -> Option A

4. Quick Check:

   Root first = Preorder [OK]

Hint: Root first means preorder traversal [OK]

Common Mistakes:

• Confusing inorder with preorder
• Thinking postorder visits root first
• Mixing level order with preorder

2. Which of the following is the correct order of nodes visited in an inorder traversal?

easy

A. Left, Right, Root

B. Root, Left, Right

C. Left, Root, Right

D. Right, Root, Left

Solution

1. Step 1: Recall inorder traversal definition

   Inorder traversal visits nodes in the order: left subtree, root, right subtree.

2. Step 2: Match with given options

   Left, Root, Right matches the left, root, right order exactly.

3. Final Answer:

   Left, Root, Right -> Option C

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Inorder always visits left subtree before root [OK]

Common Mistakes:

• Mixing preorder and inorder orders
• Assuming root is visited first in inorder
• Confusing right subtree position

3. Given the binary tree:

    A
   / \
  B   C
 /    
D   E   F

What is the postorder traversal sequence?

medium

A. D, B, E, F, C, A

B. A, B, D, E, C, F

C. B, D, E, A, C, F

D. D, E, B, F, C, A

Solution

1. Step 1: Understand postorder traversal

   Postorder visits left subtree, right subtree, then root node.

2. Step 2: Traverse given tree in postorder

   Left subtree of A: B subtree -> D, E, B; Right subtree of A: C subtree -> F, C; Finally root A.

3. Final Answer:

   D, B, E, F, C, A -> Option A

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Postorder ends with root node [OK]

Common Mistakes:

• Visiting root too early
• Mixing preorder and postorder
• Skipping right subtree nodes

4. A student wrote the preorder traversal of a tree as A, B, D, E, C, F but the inorder traversal as D, B, E, A, F, C. What is the error in the inorder traversal?

medium

A. The root node A is missing in inorder traversal

B. The nodes F and C are swapped in inorder traversal

C. The left subtree nodes are incorrectly ordered

D. No error, both traversals are consistent

Solution

1. Step 1: Analyze preorder traversal

   Preorder: root A, left subtree B with children D and E, right subtree C with child F.

2. Step 2: Check inorder traversal order

   Inorder should be left subtree (D, B, E), root A, right subtree (C, F). Given is D, B, E, A, F, C but F and C order is swapped.

3. Final Answer:

   The nodes F and C are swapped in inorder traversal -> Option B

4. Quick Check:

   Inorder right subtree order matters [OK]

Hint: Inorder right subtree nodes must be in correct order [OK]

Common Mistakes:

• Ignoring subtree order in inorder
• Assuming preorder and inorder can differ arbitrarily
• Missing root node in traversal

5. You have a binary tree where the inorder traversal is D, B, E, A, C, F and the preorder traversal is A, B, D, E, C, F. Which of the following postorder traversals is correct?

hard

A. F, C, D, E, B, A

B. B, D, E, F, C, A

C. D, B, E, C, F, A

D. D, E, B, F, C, A

Solution

1. Step 1: Use preorder to identify root and subtrees

   Preorder starts with A (root), then B subtree (D, E), then C subtree (F).

2. Step 2: Use inorder to confirm subtree nodes

   Inorder left subtree: D, B, E; right subtree: C, F.

3. Step 3: Construct postorder traversal

   Postorder visits left subtree (D, E, B), right subtree (F, C), then root (A).

4. Final Answer:

   D, E, B, F, C, A -> Option D

5. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Postorder ends with root after left and right subtrees [OK]

Common Mistakes:

• Mixing preorder and postorder sequences
• Swapping left and right subtree orders
• Placing root before subtrees in postorder