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

Concept Flow - Tree Traversal Postorder Left Right Root

Start at root

↓

Traverse left subtree

↓

Traverse right subtree

↓

Visit root node

↓

Done

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

Execution Sample

DSA Go

func postorder(node *Node) {
  if node == nil {
    return
  }
  postorder(node.Left)
  postorder(node.Right)
  fmt.Println(node.Value)
}

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

Execution Table

Step	Operation	Node Visited	Action	Tree State (Visited Nodes)
1	Start at root	A	Traverse left subtree	[]
2	Traverse left subtree	B	Traverse left subtree	[]
3	Traverse left subtree	D	Traverse left subtree	[]
4	Traverse left subtree	nil	Return (no node)	[]
5	Traverse right subtree	nil	Return (no node)	[]
6	Visit node	D	Print D	[D]
7	Traverse right subtree	E	Traverse left subtree	[D]
8	Traverse left subtree	nil	Return (no node)	[D]
9	Traverse right subtree	nil	Return (no node)	[D]
10	Visit node	E	Print E	[D, E]
11	Visit node	B	Print B	[D, E, B]
12	Traverse right subtree	C	Traverse left subtree	[D, E, B]
13	Traverse left subtree	F	Traverse left subtree	[D, E, B]
14	Traverse left subtree	nil	Return (no node)	[D, E, B]
15	Traverse right subtree	nil	Return (no node)	[D, E, B]
16	Visit node	F	Print F	[D, E, B, F]
17	Traverse right subtree	G	Traverse left subtree	[D, E, B, F]
18	Traverse left subtree	nil	Return (no node)	[D, E, B, F]
19	Traverse right subtree	nil	Return (no node)	[D, E, B, F]
20	Visit node	G	Print G	[D, E, B, F, G]
21	Visit node	C	Print C	[D, E, B, F, G, C]
22	Visit node	A	Print A	[D, E, B, F, G, C, A]

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

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 16	After Step 21	Final
Visited Nodes	[]	[D]	[D, E, B]	[D, E, B, F]	[D, E, B, F, G, C]	[D, E, B, F, G, C, A]
Current Node	A	B	B	C	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 only then the root node is visited, as shown in steps 6, 11, 16, 21, and finally 22 in the execution_table.

What happens when the node is nil during traversal?

The function returns immediately without action, as seen in steps 4, 5, 8, 9, 14, 15, 18, and 19 where traversal hits nil nodes and returns.

How does the traversal know when to stop going deeper?

It stops when it reaches a nil node (no child), returning back to the previous call, as shown in the execution_table steps where nil nodes cause returns.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes have been visited after step 11?

A [D, E]

B [D, E, B]

C [D, E, B, F]

D [D, E, B, F, G]

💡 Hint

Check the 'Tree State (Visited Nodes)' column at step 11 in the execution_table.

At which step does the traversal visit node 'F'?

A Step 16

B Step 21

C Step 13

D Step 6

💡 Hint

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

If the left child of node 'B' was nil, how would the visited nodes change after step 6?

A [D]

B []

C [E]

D [B]

💡 Hint

Step 6 visits node 'D' which is left child of 'B'; if nil, it would skip to right child 'E'.

Concept Snapshot

Postorder traversal visits nodes in this order:
1. Left subtree
2. Right subtree
3. Root node

Use recursion to traverse left, then right, then print root.
Stops when node is nil (no child).
Common for deleting trees or postfix expressions.

Full Transcript

Postorder traversal means visiting the left subtree first, then the right subtree, and finally the root node. The provided Go code recursively calls postorder 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 through the tree nodes, returning immediately when it hits a nil node (no child). The visited nodes accumulate in the order D, E, B, F, G, C, A, which matches the postorder sequence. Key moments clarify why the root is visited last, how nil nodes cause returns, and how traversal stops going deeper. The visual quiz tests understanding of visited nodes at specific steps and effects of missing children. The snapshot summarizes the traversal order and usage.

Practice

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

easy

A. Root node, Right subtree, Left subtree

B. Root node, Left subtree, Right subtree

C. Left subtree, Right subtree, Root node

D. Right subtree, Left 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: 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 C

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 Go function signatures correctly represents a recursive postorder traversal of a binary tree node root?

easy

A. func postorder(root *Node) { postorder(root.Left); postorder(root.Right); fmt.Println(root.Value) }

B. func postorder(root *Node) { fmt.Println(root.Value); postorder(root.Left); postorder(root.Right) }

C. func postorder(root *Node) { postorder(root.Right); postorder(root.Left); fmt.Println(root.Value) }

D. func postorder(root *Node) { fmt.Println(root.Value); postorder(root.Right); postorder(root.Left) }

Solution

1. Step 1: Recall postorder traversal steps

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

2. Step 2: Check function calls and print order

   func postorder(root *Node) { postorder(root.Left); postorder(root.Right); fmt.Println(root.Value) } calls postorder on left, then right, then prints root value, matching postorder.

3. Final Answer:

   func postorder(root *Node) { postorder(root.Left); postorder(root.Right); fmt.Println(root.Value) } -> Option A

4. Quick Check:

   Calls: Left, Right, Print root [OK]

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

Common Mistakes:

• Printing root before recursive calls
• Swapping left and right recursive calls
• Missing recursive calls for subtrees

3. Given the binary tree below, what is the output of the postorder traversal?

      1
     / \
    2   3
   / \
  4   5

func postorder(root *Node) { if root == nil { return } postorder(root.Left) postorder(root.Right) fmt.Print(root.Value, " ") }

medium

A. 4 2 5 3 1

B. 1 2 4 5 3

C. 2 4 5 3 1

D. 4 5 2 3 1

Solution

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

   Left subtree is rooted at 2. Postorder of subtree 2 is: left(4), right(5), root(2) -> 4 5 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), so output 3. Then print root 1 last.

3. Final Answer:

   4 5 2 3 1 -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Printing root before children
• Mixing left and right subtree order
• Skipping leaf nodes

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

func postorder(root *Node) {
  if root == nil {
    return
  }
  postorder(root.Right)
  postorder(root.Left)
  fmt.Print(root.Value, " ")
}

medium

A. The order of recursive calls is swapped; left should be before right

B. The base case is missing for nil nodes

C. The root value should be printed before recursive calls

D. The function should return a slice instead of printing

Solution

1. Step 1: Analyze recursive call order

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

2. Step 2: Recall correct postorder sequence

   Postorder requires left subtree first, then right subtree, then root. Swapping left and right causes wrong output.

3. Final Answer:

   The order of recursive calls is swapped; left should be before right -> Option A

4. Quick Check:

   Left before Right in postorder [OK]

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

Common Mistakes:

• Swapping left and right subtree calls
• Printing root before children
• Ignoring base case for nil

5. You want to collect the values of a binary tree in postorder traversal into a slice instead of printing. Which Go function correctly implements this?

hard

A. func postorder(root *Node, res *[]int) {
if root == nil {
return
}
postorder(root.Right, res)
postorder(root.Left, res)
*res = append(*res, root.Value)
}

B. func postorder(root *Node) []int {
if root == nil {
return []int{}
}
left := postorder(root.Left)
right := postorder(root.Right)
return append(left, append(right, root.Value)...)
}

C. func postorder(root *Node, res *[]int) {
if root == nil {
return
}
*res = append(*res, root.Value)
postorder(root.Left, res)
postorder(root.Right, res)
}

D. func postorder(root *Node) []int {
if root == nil {
return nil
}
return []int{root.Value}
}

Solution

1. Step 1: Understand collecting values in slice recursively

   We want a function returning a slice with postorder values: left subtree slice + right subtree slice + root value.

2. Step 2: Check each option for correct order and slice handling

   func postorder(root *Node) []int { if root == nil { return []int{} } left := postorder(root.Left) right := postorder(root.Right) return append(left, append(right, root.Value)...) } correctly returns left slice, then appends right slice, then root value, matching postorder traversal.

3. Final Answer:

   func postorder(root *Node) []int { if root == nil { return []int{} } left := postorder(root.Left) right := postorder(root.Right) return append(left, append(right, root.Value)...) } -> Option B

4. Quick Check:

   Return slices: left + right + root [OK]

Hint: Return left + right + root slices combined [OK]

Common Mistakes:

• Appending root before children slices
• Not combining slices correctly
• Returning nil instead of empty slice for nil node