Tree traversals (inorder, preorder, postorder) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Tree traversals (inorder, preorder, postorder)

Start at Root

↓

Preorder

↓

Visit Root

↓

Left

↓

Right

↓

End

Traversal starts at the root node and visits nodes in different orders depending on the method: preorder visits root first, inorder visits root between left and right, postorder visits root last.

Execution Sample

Data Structures Theory

def preorder(node):
    if node:
        print(node.val)
        preorder(node.left)
        preorder(node.right)

This code prints nodes in preorder: root, then left subtree, then right subtree.

Analysis Table

Step	Operation	Node Visited	Action	Traversal Output So Far
1	Visit Root	A	Print A	A
2	Traverse Left	B	Print B	A, B
3	Traverse Left	D	Print D	A, B, D
4	Left Child None	None	Return	A, B, D
5	Right Child None	None	Return	A, B, D
6	Traverse Right	E	Print E	A, B, D, E
7	Left Child None	None	Return	A, B, D, E
8	Right Child None	None	Return	A, B, D, E
9	Traverse Right	C	Print C	A, B, D, E, C
10	Traverse Left	F	Print F	A, B, D, E, C, F
11	Left Child None	None	Return	A, B, D, E, C, F
12	Right Child None	None	Return	A, B, D, E, C, F
13	Traverse Right	G	Print G	A, B, D, E, C, F, G
14	Left Child None	None	Return	A, B, D, E, C, F, G
15	Right Child None	None	Return	A, B, D, E, C, F, G
16	End	None	Traversal Complete	A, B, D, E, C, F, G

💡 All nodes visited, traversal complete

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 9	After Step 13	Final
Current Node	A	A	B	D	E	C	G	None
Traversal Output	[]	[A]	[A, B]	[A, B, D]	[A, B, D, E]	[A, B, D, E, C]	[A, B, D, E, C, F, G]	[A, B, D, E, C, F, G]

Key Insights - 3 Insights

Why do we print the node value before traversing children in preorder?

In preorder traversal, the root node is visited first before its children, as shown in execution_table steps 1, 2, and 3 where the node is printed before recursive calls.

Why do we return immediately when a child node is None?

When a child is None, it means there is no node to visit, so the function returns without action, as seen in steps 4, 5, 7, etc., preventing errors and ending that path.

How does the traversal output build up over time?

The output list grows step-by-step as nodes are visited and printed, tracked clearly in the 'Traversal Output So Far' column of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. Which node is visited and printed?

A Node E

B Node B

C Node D

D Node A

💡 Hint

Check the 'Node Visited' and 'Action' columns at step 3 in the execution_table.

At which step does the traversal move to the right child of node B?

A Step 6

B Step 5

C Step 9

D Step 10

💡 Hint

Look for the step where 'Traverse Right' visits node E after handling node D's children (steps 4 and 5) in the execution_table.

If we changed the traversal to inorder, when would node A be printed?

A Before visiting left subtree

B Between visiting left and right subtree

C After visiting right subtree

D Node A would not be printed

💡 Hint

Recall inorder visits left subtree first, then root, then right subtree as described in concept_flow.

Concept Snapshot

Tree Traversals:
- Preorder: Visit root, left subtree, right subtree
- Inorder: Visit left subtree, root, right subtree
- Postorder: Visit left subtree, right subtree, root
Used to process or print all nodes in a tree in different orders.

Full Transcript

Tree traversals are ways to visit all nodes in a tree. Preorder visits the root node first, then left and right children. Inorder visits left child first, then root, then right child. Postorder visits children first, then root last. The example code shows preorder traversal printing nodes as it visits them. The execution table traces each step visiting nodes A, B, D, E, C, F, G in preorder. Variables track current node and output list growing. Key moments explain why nodes print before children in preorder and why None children cause returns. The quiz tests understanding of node visits and order differences. This helps understand how trees are processed in different orders for tasks like searching or printing.

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