Tree Traversal Postorder Left Right Root in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postorder Traversal on a Simple Binary Tree

What is the output of the postorder traversal (Left, Right, Root) of the following binary tree?

Tree structure:
1
/ \
2 3
/ \
4 5

DSA Python

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

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)

result = postorder(root)
print(result)

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

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

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

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

💡 Hint

Remember postorder means visit left subtree, then right subtree, then the root node.

Postorder traversal visits nodes in the order: left child, right child, then the node itself. For the given tree, left subtree of root (1) is node 2, which has no children, so output 2 first. Then right subtree of root is node 3, whose left child is 4 and right child is 5, so visit 4, then 5, then 3. Finally visit root 1. So the output is [2, 4, 5, 3, 1].

🧠 Conceptual

intermediate

Number of Nodes Visited in Postorder Traversal

Given a binary tree with 7 nodes, how many nodes will be visited during a postorder traversal?

A Depends on the tree structure

B 6

C 8

D 7

💡 Hint

Traversal visits every node exactly once.

Postorder traversal visits every node in the tree exactly once, regardless of the tree shape. So for 7 nodes, it visits all 7 nodes.

❓ Predict Output

advanced

Postorder Traversal Output for Unbalanced Tree

What is the output of the postorder traversal for this unbalanced binary tree?

Tree structure:
10
/
5
\
7
\
9

DSA Python

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

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

root = Node(10)
root.left = Node(5)
root.left.right = Node(7)
root.left.right.right = Node(9)

result = postorder(root)
print(result)

A [9, 7, 5, 10]

B [5, 7, 9, 10]

C [9, 5, 7, 10]

D [10, 5, 7, 9]

💡 Hint

Follow left subtree first, then right subtree, then root.

The left subtree of 10 is 5, which has no left child but has right child 7, which itself has right child 9. Postorder visits left (none), then right subtree recursively, then node. So order is 9, 7, 5, then root 10.

🔧 Debug

advanced

Identify the Error in Postorder Traversal Code

What error will this code produce when performing postorder traversal?

DSA Python

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

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(postorder(root))

A The output is [3, 2, 1], which is incorrect postorder

B SyntaxError due to missing colon

C TypeError because of wrong return type

D RuntimeError due to infinite recursion

💡 Hint

Check the order of recursive calls in the return statement.

The code visits right subtree first, then left subtree, then root. This reverses the left and right order, so output is [3, 2, 1] instead of correct postorder [2, 3, 1]. No syntax or runtime error occurs.

🚀 Application

expert

Postorder Traversal Output After Node Removal

Given the binary tree below, if the node with value 3 and its subtree are removed, what is the postorder traversal output?

Tree structure:
1
/ \
2 3
/ \
4 5

DSA Python

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

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)

# Remove node 3 and its subtree
root.right = None

result = postorder(root)
print(result)

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

B [2, 1]

C [2, 4, 5, 1]

D [1, 2]

💡 Hint

Removing node 3 removes its entire subtree. Only nodes 1 and 2 remain.

After removing node 3 and its children, the tree has root 1 with left child 2 only. Postorder visits left subtree (2), then right subtree (none), then root (1). So output is [2, 1].

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