Tree Traversal Postorder Left Right Root in DSA C - Execution Trace

Concept Flow - Tree Traversal Postorder Left Right Root

Start at root node

↓

Traverse left subtree

↓

Traverse right subtree

↓

Visit current node (root)

↓

Back to parent node or end

The traversal visits left subtree first, then right subtree, and finally the root node.

Execution Sample

DSA C

void postorder(Node* root) {
  if (root == NULL) return;
  postorder(root->left);
  postorder(root->right);
  printf("%d ", root->data);
}

This code prints nodes of a binary tree in postorder: left, right, then root.

Execution Table

Step	Operation	Node Visited	Left/Right	Tree State
1	Start at root	A	root	A / \ B C / \ D E F
2	Traverse left subtree	B	left of A	A / \ B C / \ D E F
3	Traverse left subtree	D	left of B	A / \ B C / \ D E F
4	Visit node	D	leaf	D visited
5	Traverse right subtree	E	right of B	A / \ B C / \ D E F
6	Visit node	E	leaf	E visited
7	Visit node	B	after children	B visited
8	Traverse right subtree	C	right of A	A / \ B C / \ D E F
9	Traverse left subtree	null	left of C	No node
10	Traverse right subtree	F	right of C	A / \ B C / \ D E F
11	Visit node	F	leaf	F visited
12	Visit node	C	after children	C visited
13	Visit node	A	after children	A visited
14	End	null	all nodes visited	Traversal complete

💡 All nodes visited in postorder: D E B F C A

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	Final
current_node	A	B	D	D	E	E	B	C	null	F	F	C	A	null
visited_nodes	[]	[]	[]	[D]	[D]	[D, E]	[D, E, B]	[D, E, B]	[D, E, B]	[D, E, B]	[D, E, B, F]	[D, E, B, F]	[D, E, B, F, C]	[D, E, B, F, C, A]

Key Moments - 3 Insights

Why do we visit the root node after visiting left and right children?

In postorder traversal, the root is visited last after both left and right subtrees are fully visited, as shown in steps 4, 6, 7, 11, 12, and finally 13 in the execution_table.

What happens when a node has no left or right child?

When a node has no child (null), the traversal returns immediately without visiting, as in step 9 where left of C is null, so it moves on to right child.

How does the traversal know when to stop?

Traversal stops when all nodes have been visited, indicated in step 14 with 'Traversal complete' and the visited_nodes list containing all nodes.

Visual Quiz - 3 Questions

Look at the execution_table, which node is visited at step 7?

A Node B

B Node E

C Node D

D Node C

💡 Hint

Check the 'Node Visited' column at step 7 in the execution_table.

At which step does the traversal visit the root node A?

A Step 14

B Step 12

C Step 13

D Step 11

💡 Hint

Look for 'A visited' in the 'Tree State' column in the execution_table.

If node C had a left child, how would the traversal change?

A It would visit C before its left child

B It would visit the left child of C before visiting C

C It would skip the left child of C

D It would visit the left child of C after visiting C

💡 Hint

Postorder visits left subtree before the root node, see steps 8-12.

Concept Snapshot

Postorder traversal visits nodes in Left → Right → Root order.
Use recursion: traverse left subtree, then right subtree, then visit root.
Useful for deleting trees or postfix expression evaluation.
Base case: if node is NULL, return immediately.
Output order for example tree: D E B F C A.

Full Transcript

Postorder traversal means visiting the left subtree first, then the right subtree, and finally the root node. The code uses recursion to do this. Starting at the root, it goes down to the left child until it reaches a leaf. Then it visits that leaf node. After finishing the left subtree, it moves to the right subtree and does the same. Finally, it visits the root node after both children are visited. This process repeats until all nodes are visited. The example tree shows the order: D, E, B, F, C, A. When a node has no child, the function returns immediately. The traversal ends when all nodes are visited.

Practice

1. What is the correct order of nodes visited in a postorder tree traversal?

easy

A. Right subtree, Left subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Left subtree, Right subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits the left subtree first, then the right subtree, and finally the root node.

2. Step 2: Apply the order to the traversal

   Following this order ensures all children are visited before the parent node.

3. Final Answer:

   Left subtree, Right subtree, Root node -> Option D

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with the root node [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root before children
• Swapping left and right subtree order

2. Which of the following C code snippets correctly implements the postorder traversal function for a binary tree node struct Node?

easy

A. void postorder(struct Node* root) { if(root) { printf("%d ", root->data); postorder(root->left); postorder(root->right); } }

B. void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } }

C. void postorder(struct Node* root) { if(root) { postorder(root->right); postorder(root->left); printf("%d ", root->data); } }

D. void postorder(struct Node* root) { if(root) { postorder(root->left); printf("%d ", root->data); postorder(root->right); } }

Solution

1. Step 1: Check traversal order in code

   Postorder requires visiting left subtree, then right subtree, then root node.

2. Step 2: Match code to postorder steps

   void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } } calls postorder on left, then right, then prints root data, matching postorder.

3. Final Answer:

   Correct postorder traversal code -> Option B

4. Quick Check:

   Left, Right, Root in code = void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } } [OK]

Hint: Print root after left and right recursive calls [OK]

Common Mistakes:

• Printing root before children (preorder)
• Swapping left and right subtree calls
• Missing null check for root

3. Given the binary tree below:

    1
   / \
  2   3
 / \
4   5

What is the output of a postorder traversal?

medium

A. 2 4 5 3 1

B. 1 2 4 5 3

C. 4 5 2 3 1

D. 4 2 5 3 1

Solution

1. Step 1: Traverse left subtree of root (1)

   Left subtree rooted at 2: postorder visits 4, then 5, then 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), then visit root 1 last.

3. Final Answer:

   4 5 2 3 1 -> Option C

4. Quick Check:

   Left, Right, Root = 4 5 2 3 1 [OK]

Hint: Visit children fully before printing parent [OK]

Common Mistakes:

• Printing root too early
• Mixing left and right subtree order
• Confusing preorder or inorder output

4. Consider the following C function for postorder traversal:

void postorder(struct Node* root) {
    if(root == NULL) return;
    postorder(root->right);
    postorder(root->left);
    printf("%d ", root->data);
}

What is the main issue with this code?

medium

A. It visits the right subtree before the left subtree, reversing the correct order

B. It does not check if root is NULL before recursion

C. It prints the root before visiting children

D. It causes infinite recursion

Solution

1. Step 1: Analyze the order of recursive calls

   The code calls postorder on right subtree first, then left subtree, which reverses the expected left-right order.

2. Step 2: Check printing position

   Printing root after children is correct, but subtree order is wrong.

3. Final Answer:

   Visits right subtree before left, reversing order -> Option A

4. Quick Check:

   Left before right needed, code does right before left [OK]

Hint: Left subtree call must come before right subtree call [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Printing root too early
• Missing null check (not in this code though)

5. You have a binary tree where each node stores an integer. You want to collect all node values in postorder traversal into an array. Which approach correctly achieves this?

hard

A. Use recursion: traverse left subtree, traverse right subtree, then append root value to array

B. Use recursion: append root value, then traverse left and right subtrees

C. Use a queue to enqueue root first, then left and right children

D. Traverse the tree level by level and append nodes to array

Solution

1. Step 1: Understand postorder traversal for collection

   Postorder means visiting left subtree, right subtree, then root, so values must be appended in that order.

2. Step 2: Choose correct method to collect values

   Recursion that appends root after children ensures correct postorder sequence in the array.

3. Final Answer:

   Recursion: left, right, then append root -> Option A

4. Quick Check:

   Append after children = postorder collection [OK]

Hint: Append root after children for postorder array [OK]

Common Mistakes:

• Appending root before children (preorder)
• Using queue for level order, not postorder
• Confusing traversal types