Tree Traversal Postorder Left Right Root in DSA Go

Mental Model

Visit the left child, then the right child, and finally the node itself. This order ensures children are processed before their parent.

Analogy: Imagine cleaning a tree house: first clean the left room, then the right room, and only after both rooms are clean, clean the main hall.

    1
   / \
  2   3
 / \
4   5

↑ root at 1

Dry Run Walkthrough

Input: Tree: 1 with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in postorder: left subtree, right subtree, then root

Step 1: Visit left subtree of 1: move to node 2

1 -> [curr->2] -> 3
2 -> 4 -> 5

Why: We must process left child before root

Step 2: Visit left subtree of 2: move to node 4

2 -> [curr->4] -> 5

Why: Continue left before right or root

Step 3: Node 4 has no children, print 4

Printed: 4

Why: Leaf node reached, print now

Step 4: Visit right subtree of 2: move to node 5

2 -> 4 -> [curr->5]

Why: After left subtree, process right subtree

Step 5: Node 5 has no children, print 5

Printed: 4 5

Why: Leaf node reached, print now

Step 6: Print node 2 after its children

Printed: 4 5 2

Why: Children processed, now print parent

Step 7: Visit right subtree of 1: move to node 3

1 -> 2 -> [curr->3]

Why: After left subtree, process right subtree

Step 8: Node 3 has no children, print 3

Printed: 4 5 2 3

Why: Leaf node reached, print now

Step 9: Print root node 1 after its children

Printed: 4 5 2 3 1

Why: All children processed, print root last

Result:

4 5 2 3 1

Annotated Code

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func postorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    postorderTraversal(root.Left) // traverse left subtree first
    postorderTraversal(root.Right) // then traverse right subtree
    fmt.Printf("%d ", root.Val) // print root after children
}

func main() {
    // Construct the tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}

    postorderTraversal(root)
    fmt.Println()
}

postorderTraversal(root.Left) // traverse left subtree first

advance to left child to process left subtree

postorderTraversal(root.Right) // then traverse right subtree

after left subtree, process right subtree

fmt.Printf("%d ", root.Val) // print root after children

print current node after children processed

Output

4 5 2 3 1 

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative traversal, recursive is simpler but uses call stack; iterative may use explicit stack with similar time

Edge Cases

Empty tree (root is nil)

Function returns immediately without printing

DSA Go

if root == nil {
        return
    }

Single node tree

Prints the single node value

DSA Go

if root == nil {
        return
    }

When to Use This Pattern

When you need to process children before their parent in a tree, use postorder traversal to ensure left and right subtrees are handled first.

Common Mistakes

Mistake: Printing the root before children (preorder) instead of after
Fix: Move the print statement after recursive calls to left and right children

Summary

Visits left subtree, then right subtree, then the node itself.

Use when you need to process children before their parent, like deleting a tree.

The key is to print the node only after both children are processed.