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) return;
  postorder(root->left);
  postorder(root->right);
  cout << root->val << " ";
}

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

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	A	current = A	A / \ B C
2	Traverse left subtree	B	current = B	A / \ B C
3	Traverse left subtree of B	D	current = D	A / \ B C / D
4	Left of D is null	null	return	A / \ B C / D
5	Right of D is null	null	return	A / \ B C / D
6	Visit node D	D	print D	A / \ B C / D
7	Traverse right subtree of B	E	current = E	A / \ B C / \ D E
8	Left of E is null	null	return	A / \ B C / \ D E
9	Right of E is null	null	return	A / \ B C / \ D E
10	Visit node E	E	print E	A / \ B C / \ D E
11	Visit node B	B	print B	A / \ B C / \ D E
12	Traverse right subtree	C	current = C	A / \ B C
13	Left of C is null	null	return	A / \ B C
14	Right of C is null	null	return	A / \ B C
15	Visit node C	C	print C	A / \ B C
16	Visit root node	A	print A	A / \ B C
17	Traversal complete	null	return	Traversal done

💡 All nodes visited in postorder: left, right, root; traversal ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16	Final
current	null	A	B	D	D	E	B	C	A	null
printed_nodes	[]	[]	[]	[]	[D]	[D, E]	[D, E, B]	[D, E, B, C]	[D, E, B, C, A]	[D, E, B, C, A]

Key Moments - 3 Insights

Why do we print the node after traversing both left and right subtrees?

Because postorder means visiting left, then right, then the root node. The execution_table rows 4-6 and 8-10 show traversal of children before printing.

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

The function returns immediately without printing, as shown in steps 4, 5, 8, 9, 13, and 14 where null nodes cause return.

Why does the traversal start at the root but print it last?

Traversal visits children first recursively before printing the root, as seen in steps 1 (start at A) and 16 (print A last).

Visual Quiz - 3 Questions

Look at the execution_table, what nodes have been printed after step 10?

A [D, E, B]

B [D]

C [D, E]

D []

💡 Hint

Check the 'printed_nodes' variable in variable_tracker after step 10.

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

A Step 16

B Step 6

C Step 11

D Step 15

💡 Hint

Look at the 'Operation' and 'Node Visited' columns in execution_table for when 'A' is printed.

If node 'B' had no right child, how would the printed nodes after step 10 change?

A [D]

B [D, B]

C [D, E]

D [D, E, B]

💡 Hint

Without right child 'E', node 'B' would be printed after left subtree only, see steps 7-11.

Concept Snapshot

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

Full Transcript

Postorder traversal means visiting the left child first, then the right child, and finally the root node. The code uses recursion to do this. It starts at the root node, goes down to the leftmost node, prints it, then moves to the right sibling, prints it, and finally prints the parent node. This repeats up the tree until all nodes are printed. If a node is null, the function returns immediately without printing. The printed order for the example tree is D, E, B, C, A. This traversal is useful for tasks like deleting a tree or evaluating postfix expressions.

Practice

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

easy

A. Left subtree, Right subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Right subtree, Left subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits nodes in the order: left subtree first, then right subtree, and finally the root node.

2. Step 2: Match the traversal order to options

   Left subtree, Right subtree, Root node correctly lists the order as Left, Right, Root which matches postorder traversal.

3. Final Answer:

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

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with root after children [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Swapping left and right subtree order
• Thinking root is visited first

2. Which of the following C++ function signatures correctly represents a postorder traversal of a binary tree node Node*?

easy

A. void postorder(Node* root) { visit(root); postorder(root->left); postorder(root->right); }

B. void postorder(Node* root) { postorder(root->right); postorder(root->left); visit(root); }

C. void postorder(Node* root) { postorder(root->right); visit(root); postorder(root->left); }

D. void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); }

Solution

1. Step 1: Recall postorder traversal steps

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

2. Step 2: Check function calls order

   void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); } calls postorder on left, then right, then visits root, matching postorder traversal.

3. Final Answer:

   void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); } -> Option D

4. Quick Check:

   Left, Right, Root call order = void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); } [OK]

Hint: Postorder calls left, then right, then root visit [OK]

Common Mistakes:

• Visiting root before children (preorder)
• Swapping left and right subtree calls
• Missing visit call after recursion

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a postorder traversal?

medium

A. [1, 2, 3, 4, 5]

B. [4, 2, 5, 3, 1]

C. [4, 5, 2, 3, 1]

D. [2, 4, 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 alone, visited next. Finally, root 1 is visited.

3. Final Answer:

   [4, 5, 2, 3, 1] -> Option C

4. Quick Check:

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

Hint: Visit children fully before root [OK]

Common Mistakes:

• Listing root before children
• Mixing left and right subtree order
• Confusing with preorder or inorder output

4. The following C++ code attempts postorder traversal but produces incorrect output. What is the error?

void postorder(Node* root) {
  if (!root) return;
  postorder(root->right);
  postorder(root->left);
  visit(root);
}

medium

A. Left and right subtree calls are swapped

B. The base case check is incorrect

C. The visit call is missing

D. The function should visit root before children

Solution

1. Step 1: Analyze recursive calls order

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

2. Step 2: Understand correct postorder order

   Postorder requires left subtree first, then right subtree, then root visit.

3. Final Answer:

   Left and right subtree calls are swapped -> Option A

4. Quick Check:

   Left before right in postorder [OK]

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

Common Mistakes:

• Swapping left and right subtree calls
• Visiting root before children
• Omitting base case check

5. You want to collect all node values of a binary tree in postorder traversal into a vector. Which code snippet correctly implements this in C++?

hard

A. void postorder(Node* root, vector<int>& res) { if (!root) return; res.push_back(root->val); postorder(root->left, res); postorder(root->right, res); }

B. void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); }

C. void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->right, res); postorder(root->left, res); res.push_back(root->val); }

D. void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); res.push_back(root->val); postorder(root->right, res); }

Solution

1. Step 1: Confirm traversal order in code

   void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } calls postorder on left, then right subtree, then adds root value to vector, matching postorder.

2. Step 2: Check other options for order mistakes

   The other options either add the root value too early or swap left and right calls, breaking postorder.

3. Final Answer:

   void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } -> Option B

4. Quick Check:

   Left, Right, Root push_back order = void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } [OK]

Hint: Push root value after left and right recursion [OK]

Common Mistakes:

• Pushing root value before children
• Swapping left and right subtree calls
• Forgetting to check for null root