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

Concept Flow - Tree Traversal Postorder Left Right Root

Start at root node

↓

Traverse left subtree

↓

Traverse right subtree

↓

Visit current node (root)

↓

Return to parent node

↓

Repeat until all nodes visited

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

Execution Sample

DSA Java

void postorder(Node node) {
  if (node == null) return;
  postorder(node.left);
  postorder(node.right);
  System.out.print(node.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	Output
1	Start at root	A	root	A / \ B C
2	Traverse left subtree	B	left	A / \ B C
3	Traverse left subtree of B	D	left	A / \ B C / D
4	Traverse left subtree of D	null	left	A / \ B C / D
5	Traverse right subtree of D	null	right	A / \ B C / D
6	Visit node D	D	root	A / \ B C / D	D
7	Traverse right subtree of B	E	right	A / \ B C / \ D E	D
8	Traverse left subtree of E	null	left	A / \ B C / \ D E	D
9	Traverse right subtree of E	null	right	A / \ B C / \ D E	D
10	Visit node E	E	root	A / \ B C / \ D E	D E
11	Visit node B	B	root	A / \ B C / \ D E	D E B
12	Traverse right subtree	C	right	A / \ B C	D E B
13	Traverse left subtree of C	null	left	A / \ B C	D E B
14	Traverse right subtree of C	null	right	A / \ B C	D E B
15	Visit node C	C	root	A / \ B C	D E B C
16	Visit root node	A	root	A / \ B C	D E B C A
17	Traversal complete	null	none	A / \ B C	D E B C A

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

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 11	After Step 15	Final
Current Node	A	B	D	B	C	null
Output	""	""	D	D E B	D E B C	D E B C A

Key Moments - 3 Insights

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

Because postorder traversal means visiting left subtree first, then right subtree, and only then the root node, as shown in steps 6, 10, 11, 15, and 16 in the execution_table.

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

The traversal calls the function with null, which immediately returns without output, as seen in steps 4, 5, 8, 9, 13, and 14.

How does the traversal know when it is done?

When all nodes have been visited and the recursive calls return back to the original root, as shown in step 17 where traversal completes.

Visual Quiz - 3 Questions

Look at the execution_table, what is the output after visiting node E (step 10)?

A "D E B "

B "D "

C "D E "

D "D E B C A "

💡 Hint

Check the Output column at step 10 in the execution_table.

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

A Step 16

B Step 11

C Step 15

D Step 17

💡 Hint

Look for 'Visit root node' operation in the execution_table.

If node C had a left child, how would the output change after step 15?

A Output would include that child's data after C

B Output would include that child's data before C

C Output would be the same as step 15

D Output would not include node C

💡 Hint

Postorder visits left subtree before the node itself, see traversal order in execution_table.

Concept Snapshot

Postorder traversal visits nodes in this order:
1. Left subtree
2. Right subtree
3. Root node
Use recursion:
- Call postorder on left child
- Call postorder on right child
- Process current node
This ensures children are processed before their parent.

Full Transcript

Postorder traversal of a binary tree means visiting the left subtree first, then the right subtree, and finally the root node. The provided Java code recursively calls the postorder function on the left child, then the right child, and then prints the current node's data. The execution table shows step-by-step how the traversal moves through nodes A, B, D, E, and C, printing their values only after visiting their children. Null children cause immediate return without output. The traversal ends after all nodes are visited, producing the output sequence D E B C A.

Practice

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

easy

A. Root node, Left subtree, Right subtree

B. Left subtree, Right subtree, Root node

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 order with options

   Left subtree, Right subtree, Root node matches the order Left, Right, Root exactly.

3. Final Answer:

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

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
• Visiting root before children
• Swapping left and right subtree order

2. Which of the following Java method signatures correctly represents a recursive postorder traversal of a binary tree node named root?

easy

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

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

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

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

Solution

1. Step 1: Recall postorder traversal steps

   Postorder visits left subtree, then right subtree, then root node (visit).

2. Step 2: Check each method's order

   void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } calls postorder on left, then right, then visits root, matching postorder correctly.

3. Final Answer:

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

4. Quick Check:

   Left, Right, Root method order = void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } [OK]

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

Common Mistakes:

• Visiting root before children
• Swapping left and right recursive calls
• Using visit instead of recursive call for children

3. Given the binary tree below:

    1
   / \
  2   3
 / \
4   5

What is the output of the postorder traversal?

medium

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

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

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 (left), 5 (right), then 2 (root) -> [4, 5, 2]

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), so visit 3, then visit root 1 -> [3, 1]

3. Step 3: Combine all parts

   Full postorder: left subtree [4,5,2], right subtree [3], root [1] -> [4, 5, 2, 3, 1]

4. Final Answer:

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

5. Quick Check:

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

Hint: Visit left subtree fully, then right, then root last [OK]

Common Mistakes:

• Visiting root before children
• Mixing up left and right subtree order
• Outputting preorder or inorder instead

4. Consider this Java method for postorder traversal:

void postorder(Node root) {
  if (root == null) return;
  postorder(root.right);
  postorder(root.left);
  visit(root);
}

What is the main problem with this code?

medium

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

B. It causes infinite recursion

C. It visits the root before children

D. It does not check for null root

Solution

1. Step 1: Analyze traversal order in code

   The code calls postorder on right subtree first, then left subtree, then visits root.

2. Step 2: Compare with correct postorder order

   Correct postorder is left, right, root. This code reverses left and right subtree order.

3. Final Answer:

   It visits right subtree before left subtree, reversing order -> Option A

4. Quick Check:

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

Hint: Left subtree must be visited before right in postorder [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Ignoring null check (though present here)
• Visiting root before children

5. You want to collect all node values of a binary tree in postorder traversal into a list. Which of the following Java code snippets correctly implements this?

hard

A. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); result.add(root.val); postorder(root.right, result); }

B. void postorder(Node root, List<Integer> result) { if(root==null) return; result.add(root.val); postorder(root.left, result); postorder(root.right, result); }

C. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.right, result); postorder(root.left, result); result.add(root.val); }

D. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); }

Solution

1. Step 1: Understand postorder traversal with list collection

   Postorder visits left subtree, then right subtree, then adds root value to list.

2. Step 2: Check each code snippet's order

   void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } calls postorder on left, then right, then adds root value last, matching postorder correctly.

3. Final Answer:

   void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } -> Option D

4. Quick Check:

   Left, Right, Root with result.add last = void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } [OK]

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

Common Mistakes:

• Adding root value before children
• Swapping left and right subtree calls
• Forgetting null check before recursion