Tree traversals (inorder, preorder, postorder) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is inorder traversal in a binary tree?

Inorder traversal visits nodes in this order: left child, current node, then right child. It is often used to get nodes in ascending order for binary search trees.

beginner

Describe preorder traversal of a tree.

Preorder traversal visits nodes in this order: current node first, then left child, then right child. It is useful for copying trees or getting prefix expressions.

beginner

What is the order of visiting nodes in postorder traversal?

Postorder traversal visits nodes in this order: left child, right child, then current node. It is often used to delete trees or evaluate postfix expressions.

intermediate

Why is inorder traversal important for binary search trees?

Because inorder traversal visits nodes in ascending order, it helps retrieve sorted data from a binary search tree.

intermediate

Which traversal would you use to copy a tree structure exactly as it is?

Preorder traversal is best for copying a tree because it visits the root node before its children, preserving the structure.

In which traversal is the root node visited first?

A Preorder

B Inorder

C Postorder

D Level order

Preorder traversal visits the root node first, then left and right children.

Which traversal visits nodes in ascending order for a binary search tree?

A Preorder

B Inorder

C Postorder

D Level order

Inorder traversal visits nodes in ascending order in a binary search tree.

What is the last node visited in postorder traversal?

A Root node

B Right child

C Left child

D None of the above

Postorder traversal visits the root node last, after its children.

Which traversal is commonly used to delete all nodes in a tree safely?

A Preorder

B Inorder

C Postorder

D Level order

Postorder traversal visits children before the parent, making it safe to delete nodes.

If you want to print the root node before its children, which traversal do you choose?

A None

B Inorder

C Postorder

D Preorder

Preorder traversal prints the root node before its children.

Explain the difference between inorder, preorder, and postorder tree traversals.

Think about the position of the root node in each traversal.

Describe a real-life situation where you might use postorder traversal.

Consider tasks that require finishing work on parts before the whole.

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