Tree Traversal Postorder Left Right Root in DSA Python - 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 if root

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

Execution Sample

DSA Python

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

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

Execution Table

Step	Operation	Node Visited	Action	Tree State (Visual)
1	Start at root	A	Traverse left subtree	A ├─B │ ├─D │ └─E └─C ├─F └─G
2	Traverse left subtree	B	Traverse left subtree	Same as above
3	Traverse left subtree	D	Traverse left subtree (None)	Same as above
4	Left None	None	Return	Same as above
5	Traverse right subtree	D	Traverse right subtree (None)	Same as above
6	Right None	None	Return	Same as above
7	Visit node	D	Print D	D visited
8	Traverse right subtree	B	Traverse right subtree	Same as above
9	Traverse left subtree	E	Traverse left subtree (None)	Same as above
10	Left None	None	Return	Same as above
11	Traverse right subtree	E	Traverse right subtree (None)	Same as above
12	Right None	None	Return	Same as above
13	Visit node	E	Print E	E visited
14	Visit node	B	Print B	B visited
15	Traverse right subtree	A	Traverse right subtree	Same as above
16	Traverse left subtree	C	Traverse left subtree	Same as above
17	Traverse left subtree	F	Traverse left subtree (None)	Same as above
18	Left None	None	Return	Same as above
19	Traverse right subtree	F	Traverse right subtree (None)	Same as above
20	Right None	None	Return	Same as above
21	Visit node	F	Print F	F visited
22	Traverse right subtree	C	Traverse right subtree	Same as above
23	Traverse left subtree	G	Traverse left subtree (None)	Same as above
24	Left None	None	Return	Same as above
25	Traverse right subtree	G	Traverse right subtree (None)	Same as above
26	Right None	None	Return	Same as above
27	Visit node	G	Print G	G visited
28	Visit node	C	Print C	C visited
29	Visit node	A	Print A	A visited
30	End	None	Traversal complete	All nodes visited in order D E B F G C A

💡 Traversal ends after visiting root node A following left and right subtrees.

Variable Tracker

Variable	Start	After Step 7	After Step 13	After Step 14	After Step 21	After Step 27	After Step 28	After Step 29
Current Node	A	D	E	B	F	G	C	A
Visited Nodes	[]	[D]	[D, E]	[D, E, B]	[D, E, B, F]	[D, E, B, F, G]	[D, E, B, F, G, C]	[D, E, B, F, G, C, A]

Key Moments - 3 Insights

Why do we visit the root node last in postorder traversal?

Because postorder means left subtree first, then right subtree, and finally the root node, as shown in steps 7, 13, 14, 21, 27, 28, and 29 in the execution_table.

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

The traversal returns immediately when it encounters None (no child), as seen in steps 4, 6, 10, 12, 18, 20, 24, and 26, allowing the recursion to backtrack.

How does the traversal know when to stop?

It stops after visiting the root node last (step 29) and no more nodes remain to visit, as indicated by the exit note.

Visual Quiz - 3 Questions

Look at the execution_table, what node is visited at step 21?

A G

B F

C C

D B

💡 Hint

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

At which step does the traversal visit node E?

A Step 7

B Step 14

C Step 13

D Step 27

💡 Hint

Look for 'Visit node' action with node E in the execution_table.

If node B had no right child, which step would be skipped?

A Step 8 (Traverse right subtree of B)

B Step 14 (Visit B)

C Step 13 (Visit E)

D Step 7 (Visit D)

💡 Hint

Check the steps related to traversing right subtree of B in the execution_table.

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.
Stops when all nodes are visited.
Print or process node only after children are done.

Full Transcript

Postorder tree traversal means visiting the left subtree first, then the right subtree, and finally the root node. The provided code recursively calls itself on the left child, then the right child, and prints the node's value last. The execution table shows step-by-step how the traversal moves down to the leftmost node, backtracks after reaching None children, and visits nodes in the order D, E, B, F, G, C, A. Variables track the current node and the list of visited nodes after each visit. Key moments clarify why the root is visited last, how None children cause backtracking, and when traversal ends. The visual quiz tests understanding of node visits at specific steps and the effect of missing children. The snapshot summarizes the traversal order and usage. This trace helps beginners see exactly how postorder traversal works on a binary tree.

Practice

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

easy

A. Root node, Left subtree, Right subtree

B. Right subtree, Left subtree, Root node

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 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 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 node first instead of last
• Swapping left and right subtree order

2. Which of the following Python function headers correctly defines a postorder traversal method for a binary tree node root?

easy

A. def postorder(root):

B. def preorder(root):

C. def inorder(root):

D. def traverse(root):

Solution

1. Step 1: Identify the function name for postorder traversal

   The function name should clearly indicate postorder traversal, so postorder is correct.

2. Step 2: Check the parameter

   The parameter root is standard for the current node in tree traversal functions.

3. Final Answer:

   def postorder(root): -> Option A

4. Quick Check:

   Function name matches traversal type [OK]

Hint: Function name should match traversal type exactly [OK]

Common Mistakes:

• Using wrong traversal names like preorder or inorder
• Missing the root parameter
• Using generic names that don't specify traversal

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of the postorder traversal?

medium

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

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

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

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

Solution

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

   Left subtree rooted at 2: postorder is left (4), right (5), root (2) -> [4, 5, 2]

2. Step 2: Traverse right subtree of root (1)

   Right subtree rooted at 3 has no children, so postorder is [3]

3. Step 3: Combine left, right, and root

   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 A

5. Quick Check:

   Postorder = Left, Right, Root [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
• Listing nodes in preorder or inorder instead

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

def postorder(root):
    if root:
        print(root.data)
        postorder(root.left)
        postorder(root.right)

medium

A. The left and right subtree calls are swapped

B. The function does not check if root is None

C. The root node is printed before traversing children

D. The function should return a list instead of printing

Solution

1. Step 1: Analyze the order of print and recursive calls

   The code prints root.data first, then traverses left and right subtrees. This is preorder traversal order.

2. Step 2: Identify correct postorder sequence

   Postorder requires visiting left subtree, then right subtree, then printing root last.

3. Final Answer:

   The root node is printed before traversing children -> Option C

4. Quick Check:

   Print after children calls for postorder [OK]

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

Common Mistakes:

• Printing root before children (preorder mistake)
• Not handling empty nodes properly
• Swapping left and right subtree calls

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

hard

A. def postorder(root):
result = []
if root:
result.append(root.data)
result += postorder(root.left)
result += postorder(root.right)
return result

B. def postorder(root):
result = []
if root:
result += postorder(root.left)
result += postorder(root.right)
result.append(root.data)
return result

C. def postorder(root):
if root is None:
return []
return [root.data] + postorder(root.left) + postorder(root.right)

D. def postorder(root):
if root is None:
return []
return postorder(root.left) + [root.data] + postorder(root.right)

Solution

1. Step 1: Check the order of appending nodes

   def postorder(root): result = [] if root: result += postorder(root.left) result += postorder(root.right) result.append(root.data) return result appends left subtree results, then right subtree results, then root data last, matching postorder.

2. Step 2: Verify return of combined list

   def postorder(root): result = [] if root: result += postorder(root.left) result += postorder(root.right) result.append(root.data) return result returns the combined list correctly after recursive calls.

3. Final Answer:

   def postorder(root): result = [] if root: result += postorder(root.left) result += postorder(root.right) result.append(root.data) return result -> Option B

4. Quick Check:

   Left + Right + Root order in list [OK]

Hint: Append root after left and right recursive results [OK]

Common Mistakes:

• Appending root before children (preorder)
• Incorrect list concatenation order
• Not returning the combined list properly