Tree Traversal Postorder Left Right Root in DSA Python

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 finally the main hall where you started.

    1
   / \
  2   3
 / \
4   5
↑ root

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: Traverse left subtree of 1 (node 2)

    1
   / \
  [2] 3
 / \
4   5
↑ curr at 2

Why: We must visit left child before root

Step 2: Traverse left subtree of 2 (node 4)

    1
   / \
  2   3
 / \
[4]  5
↑ curr at 4

Why: Continue going left to reach leaf

Step 3: Visit node 4 (leaf), print 4

4

Why: Left and right children are null, so print node

Step 4: Traverse right subtree of 2 (node 5)

    1
   / \
  2   3
 / \
4  [5]
↑ curr at 5

Why: After left subtree, visit right subtree

Step 5: Visit node 5 (leaf), print 5

4 5

Why: Left and right children are null, so print node

Step 6: Visit node 2 after its children, print 2

4 5 2

Why: After left and right children, print parent

Step 7: Traverse right subtree of 1 (node 3)

    1
   / \
  2  [3]
 / \
4   5
↑ curr at 3

Why: After left subtree of root, visit right subtree

Step 8: Visit node 3 (leaf), print 3

4 5 2 3

Why: No children, print node

Step 9: Visit root node 1 after children, print 1

4 5 2 3 1

Why: After left and right subtrees, print root

Result:

4 5 2 3 1

Annotated Code

DSA Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorder_traversal(root):
    result = []
    def traverse(node):
        if node is None:
            return
        traverse(node.left)  # visit left subtree
        traverse(node.right) # visit right subtree
        result.append(node.val) # visit root last
    traverse(root)
    return result

# Build tree from dry_run input
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)

output = postorder_traversal(root)
print(' '.join(map(str, output)))

if node is None: return

stop recursion at leaf's child

traverse(node.left) # visit left subtree

go left first

traverse(node.right) # visit right subtree

then go right

result.append(node.val) # visit root last

add current node after children

Output

4 5 2 3 1

Complexity Analysis

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

Space: O(n) due to recursion stack in worst case (skewed tree) and output list

vs Alternative: Compared to preorder or inorder, postorder also visits all nodes once, so same time complexity; iterative versions may use explicit stacks.

Edge Cases

Empty tree (root is None)

Returns empty list without error

DSA Python

if node is None:
    return

Single node tree

Returns list with single node value

DSA Python

result.append(node.val) # visit root last

Tree with only left children

Visits nodes from bottom left up to root

DSA Python

traverse(node.left)  # visit left subtree

When to Use This Pattern

When a problem requires processing children before their parent, especially for deleting or evaluating expressions, use postorder traversal.

Common Mistakes

Mistake: Appending node value before traversing children (preorder instead of postorder)
Fix: Move the append operation after traversing 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 or evaluating expressions.

The key is to visit children fully before the parent node.

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