Binary Tree Postorder Traversal

🎯

Binary Tree Postorder Traversal

easyTREEAmazonMicrosoft

Imagine you are building a file system explorer that needs to delete files and folders in the correct order, starting from the deepest files and moving up to the root folder. This requires visiting nodes in postorder.

💡 This problem is about traversing a binary tree in a specific order: left subtree, right subtree, then the node itself. Beginners often struggle because postorder traversal is less intuitive than preorder or inorder, and recursive and iterative solutions differ significantly.

📋

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes' values. Postorder traversal visits the left subtree, then the right subtree, and finally the node itself.

The number of nodes in the tree is in the range [1, 10^5].-10^9 <= Node.val <= 10^9

💡

Example

Input"root = [1,null,2,3]"

Output[3,2,1]

The tree is: 1 -> right child 2 -> left child 3. Postorder visits left (3), right (2), then root (1).

• Single node tree → output is the node itself
• Tree with only left children → output is nodes from bottom to top
• Tree with only right children → output is nodes from bottom to top
• Empty tree (null root) → output is an empty list

⚠️

Common Mistakes

Appending node value before traversing right subtree

Output order becomes incorrect, resembling preorder instead of postorder

✅ Ensure node value is appended only after left and right subtrees are fully traversed

Not handling null root input

Code throws null pointer exception or runtime error

✅ Add a check at the start to return empty list if root is null

In iterative one-stack approach, not tracking last visited node

Infinite loop or revisiting nodes multiple times

✅ Use a variable to track last visited node to know when to visit or traverse right subtree

Pushing children in wrong order in two-stack approach

Final output order is incorrect because reversal logic breaks

✅ Push left child first, then right child to stack1 to ensure correct order in stack2

🧠

Brute Force (Pure Recursion)

💡 Starting with recursion helps understand the natural definition of postorder traversal and builds intuition before optimizing or switching to iterative methods.

Intuition

Postorder traversal means visiting left subtree, then right subtree, then the node itself. Recursion naturally mirrors this definition by calling itself on subtrees before processing the node.

Algorithm

1. If the current node is null, return.
2. Recursively traverse the left subtree.
3. Recursively traverse the right subtree.
4. Add the current node's value to the result list.

💡 The recursion stack implicitly remembers where you are, so you don't need to manage your own stack or list of nodes.

</>

Code

from typing import Optional, List

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

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)
    dfs(root)
    return result

# Example usage:
# root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
# print(postorderTraversal(root))  # Output: [3,2,1]

Line Notes

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:Defines the main function signature for clarity and type safety.

result = []Initialize a list to store the traversal order as we visit nodes.

if not node:Base case to stop recursion when reaching a null child.

result.append(node.val)Add the node's value after visiting left and right subtrees to ensure postorder.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) return;
        dfs(node.left, result);
        dfs(node.right, result);
        result.add(node.val);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.right = new TreeNode(2);
    //     root.right.left = new TreeNode(3);
    //     Solution sol = new Solution();
    //     System.out.println(sol.postorderTraversal(root)); // [3,2,1]
    // }
}

Line Notes

public List<Integer> postorderTraversal(TreeNode root)Main method to start traversal and return results.

List<Integer> result = new ArrayList<>();Stores the traversal output in order.

if (node == null) return;Stops recursion at leaf nodes' children.

result.add(node.val);Adds node value after left and right children are processed.

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root, result);
        return result;
    }
private:
    void dfs(TreeNode* node, vector<int>& result) {
        if (!node) return;
        dfs(node->left, result);
        dfs(node->right, result);
        result.push_back(node->val);
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->right = new TreeNode(2);
//     root->right->left = new TreeNode(3);
//     Solution sol;
//     vector<int> res = sol.postorderTraversal(root);
//     for (int v : res) cout << v << ' '; // Output: 3 2 1
//     return 0;
// }

Line Notes

vector<int> postorderTraversal(TreeNode* root)Function signature returning vector of node values.

vector<int> result;Stores the postorder traversal result.

if (!node) return;Base case to stop recursion at null nodes.

result.push_back(node->val);Add current node's value after traversing children.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function postorderTraversal(root) {
    const result = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        dfs(node.right);
        result.push(node.val);
    }
    dfs(root);
    return result;
}

// Example usage:
// const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
// console.log(postorderTraversal(root)); // [3,2,1]

Line Notes

function postorderTraversal(root)Defines main traversal function accepting root node.

const result = []Array to collect traversal output.

if (!node) return;Stops recursion when node is null.

result.push(node.val)Push node value after left and right subtrees are visited.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, so time is linear. Space is O(n) due to recursion stack in worst case (skewed tree) and output list.

💡 For a tree with 20 nodes, this means about 20 function calls and storing 20 values, which is efficient for interview constraints.

Interview Verdict: Accepted

This approach is accepted and often the first solution to implement in interviews because it is simple and directly follows the problem definition.

🧠

Iterative Using Two Stacks

💡 Iterative solutions avoid recursion stack overflow and demonstrate understanding of traversal order manipulation, which is valuable in interviews.

Intuition

Postorder can be simulated by modifying preorder traversal: if preorder is root-left-right, then reverse the order to root-right-left and finally reverse the output to get left-right-root.

Algorithm

1. Push root to stack1.
2. While stack1 is not empty, pop from stack1 and push it to stack2.
3. Push left and right children of popped node to stack1.
4. After processing all nodes, pop all nodes from stack2 to get postorder.

💡 Two stacks help reverse the order of node processing to achieve postorder without recursion.

</>

Code

from typing import Optional, List

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

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    return [node.val for node in reversed(stack2)]

# Example usage:
# root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
# print(postorderTraversal(root))  # Output: [3,2,1]

Line Notes

if not root:Handle empty tree edge case immediately.

stack1, stack2 = [root], []Initialize two stacks; stack1 for processing, stack2 for reversed output.

node = stack1.pop()Pop node to process from stack1.

return [node.val for node in reversed(stack2)]Reverse stack2 to get correct postorder traversal.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) stack1.push(node.left);
            if (node.right != null) stack1.push(node.right);
        }
        while (!stack2.isEmpty()) {
            result.add(stack2.pop().val);
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.right = new TreeNode(2);
    //     root.right.left = new TreeNode(3);
    //     Solution sol = new Solution();
    //     System.out.println(sol.postorderTraversal(root)); // [3,2,1]
    // }
}

Line Notes

if (root == null) return result;Return empty list if tree is empty.

Stack<TreeNode> stack1 = new Stack<>();Stack1 for processing nodes in modified preorder.

stack2.push(node);Stack2 collects nodes in reverse postorder.

while (!stack2.isEmpty()) { result.add(stack2.pop().val); }Pop from stack2 to get correct postorder.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<TreeNode*> stack1, stack2;
        stack1.push(root);
        while (!stack1.empty()) {
            TreeNode* node = stack1.top(); stack1.pop();
            stack2.push(node);
            if (node->left) stack1.push(node->left);
            if (node->right) stack1.push(node->right);
        }
        while (!stack2.empty()) {
            result.push_back(stack2.top()->val);
            stack2.pop();
        }
        return result;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->right = new TreeNode(2);
//     root->right->left = new TreeNode(3);
//     Solution sol;
//     vector<int> res = sol.postorderTraversal(root);
//     for (int v : res) cout << v << ' '; // Output: 3 2 1
//     return 0;
// }

Line Notes

if (!root) return result;Handle empty tree edge case.

stack<TreeNode*> stack1, stack2;Two stacks to simulate postorder traversal.

stack2.push(node);Push nodes to stack2 to reverse processing order.

while (!stack2.empty()) { result.push_back(stack2.top()->val);Extract nodes from stack2 to get postorder.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function postorderTraversal(root) {
    if (!root) return [];
    const stack1 = [root], stack2 = [];
    while (stack1.length) {
        const node = stack1.pop();
        stack2.push(node);
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    return stack2.reverse().map(node => node.val);
}

// Example usage:
// const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
// console.log(postorderTraversal(root)); // [3,2,1]

Line Notes

if (!root) return [];Return empty array if tree is empty.

const stack1 = [root], stack2 = [];Initialize two stacks for iterative traversal.

stack2.push(node);Push nodes to stack2 to reverse the order.

return stack2.reverse().map(node => node.val);Reverse stack2 and extract values for postorder.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is pushed and popped at most twice, so linear time. Space is linear due to stacks and output list.

💡 For 20 nodes, this means about 40 stack operations plus storing 20 values, still efficient and safe from recursion limits.

Interview Verdict: Accepted

This approach is accepted and useful when recursion is not allowed or stack overflow is a concern.

🧠

Iterative Using One Stack and a Pointer

💡 This approach is more complex but uses only one stack and a pointer to track traversal, demonstrating mastery of iterative tree traversal.

Intuition

Use a stack to traverse down the tree, pushing nodes. Track the last visited node to know when to visit the current node or move to right subtree.

Algorithm

1. Initialize an empty stack and set current node to root.
2. While current is not null or stack is not empty:
3. Traverse left subtree pushing nodes onto stack.
4. Peek the top node; if it has a right child not yet visited, move to right child.
5. Otherwise, visit the node and pop it from stack.

💡 Tracking last visited node helps decide when to visit a node or explore its right subtree, avoiding revisiting nodes.

</>

Code

from typing import Optional, List

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

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

# Example usage:
# root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
# print(postorderTraversal(root))  # Output: [3,2,1]

Line Notes

stack = []Stack to keep track of nodes to visit.

last_visited = NoneTracks last node visited to avoid revisiting right subtree.

while current:Traverse left subtree pushing nodes.

if peek_node.right and last_visited != peek_node.right:Decide whether to traverse right subtree or visit node.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode lastVisited = null;
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            TreeNode peekNode = stack.peek();
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                result.add(peekNode.val);
                lastVisited = stack.pop();
            }
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.right = new TreeNode(2);
    //     root.right.left = new TreeNode(3);
    //     Solution sol = new Solution();
    //     System.out.println(sol.postorderTraversal(root)); // [3,2,1]
    // }
}

Line Notes

Deque<TreeNode> stack = new ArrayDeque<>();Stack implemented with Deque for efficient push/pop.

TreeNode lastVisited = null;Tracks last visited node to control traversal.

while (current != null) { stack.push(current); current = current.left; }Traverse left subtree pushing nodes.

if (peekNode.right != null && lastVisited != peekNode.right)Check if right subtree needs to be traversed.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stack;
        TreeNode* lastVisited = nullptr;
        TreeNode* current = root;
        while (current || !stack.empty()) {
            while (current) {
                stack.push(current);
                current = current->left;
            }
            TreeNode* peekNode = stack.top();
            if (peekNode->right && lastVisited != peekNode->right) {
                current = peekNode->right;
            } else {
                result.push_back(peekNode->val);
                lastVisited = peekNode;
                stack.pop();
            }
        }
        return result;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->right = new TreeNode(2);
//     root->right->left = new TreeNode(3);
//     Solution sol;
//     vector<int> res = sol.postorderTraversal(root);
//     for (int v : res) cout << v << ' '; // Output: 3 2 1
//     return 0;
// }

Line Notes

stack<TreeNode*> stack;Stack to hold nodes during traversal.

TreeNode* lastVisited = nullptr;Tracks last visited node to avoid revisiting.

while (current) { stack.push(current); current = current->left; }Traverse left subtree pushing nodes.

if (peekNode->right && lastVisited != peekNode->right)Decide whether to traverse right subtree or visit node.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function postorderTraversal(root) {
    const result = [];
    const stack = [];
    let lastVisited = null;
    let current = root;
    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        let peekNode = stack[stack.length - 1];
        if (peekNode.right && lastVisited !== peekNode.right) {
            current = peekNode.right;
        } else {
            result.push(peekNode.val);
            lastVisited = stack.pop();
        }
    }
    return result;
}

// Example usage:
// const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
// console.log(postorderTraversal(root)); // [3,2,1]

Line Notes

const stack = [];Stack to keep track of nodes.

let lastVisited = null;Tracks last visited node to control traversal.

while (current) { stack.push(current); current = current.left; }Traverse left subtree pushing nodes.

if (peekNode.right && lastVisited !== peekNode.right)Check if right subtree needs traversal.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is pushed and popped once, so linear time. Space is linear due to stack and output list.

💡 For 20 nodes, this means about 20 stack operations and storing 20 values, efficient and avoids recursion.

Interview Verdict: Accepted

This approach is accepted and preferred when interviewers want iterative solutions with minimal extra space.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the recursive approach is sufficient and fastest to implement. Iterative approaches are useful when recursion is disallowed or stack overflow is a concern.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(n) due to recursion stack	Yes (deep recursion on skewed trees)	N/A	Mention and code first; simplest to explain
2. Iterative Using Two Stacks	O(n)	O(n) due to two stacks	No	N/A	Good to mention for iterative solution; safe from recursion limits
3. Iterative Using One Stack and Pointer	O(n)	O(n) due to one stack	No	N/A	Best iterative approach; shows mastery but more complex to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force recursive approach, followed by iterative methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the recursive postorder traversal approach.Step 3: Implement the recursive solution and test.Step 4: Discuss iterative approaches and their tradeoffs.Step 5: Implement an iterative solution if time permits.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal orders, recursion, iterative conversion, and handling edge cases like empty or skewed trees.

Common Follow-ups

• Can you implement postorder traversal iteratively without using two stacks? → Use one stack and a pointer to track last visited node.
• What is the space complexity of your recursive solution? → O(h) where h is tree height due to recursion stack.

💡 These follow-ups test your ability to optimize space and convert recursive logic to iterative, common interview challenges.

🔍

Pattern Recognition

When to Use

1) Problem involves visiting all nodes in a binary tree; 2) Output order is left subtree, right subtree, then node; 3) Recursive or iterative traversal is required; 4) Postorder traversal is explicitly or implicitly requested.

Signature Phrases

postorder traversalleft subtree, right subtree, then nodevisit children before parent

NOT This Pattern When

Problems that require level order traversal or BFS are different patterns.

Similar Problems

Binary Tree Inorder Traversal - similar but visits node between left and rightBinary Tree Preorder Traversal - visits node before childrenN-ary Tree Postorder Traversal - generalizes postorder to trees with more than two children

Practice

1. Consider the following iterative postorder traversal code to check if a binary tree is balanced. Given the tree: root=1, left=2, right=3, and node 2 has left child 4. What is the value of heights[root] after the traversal completes?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace heights for leaf nodes

   Node 4 is a leaf, so heights[4] = 1.

2. Step 2: Compute heights bottom-up

   Node 2 has left child 4 (height 1) and no right child (height 0), so heights[2] = 1 + max(1,0) = 2. Node 3 is leaf, heights[3] = 1. Root 1 has children heights 2 and 1, so heights[1] = 1 + max(2,1) = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Height of root is max height of subtrees plus one [OK]

Hint: Height of root equals max subtree height plus one [OK]

Common Mistakes:

• Forgetting to add 1 for current node height
• Mixing up left and right subtree heights
• Returning height instead of boolean balance

2. You are given a binary tree and asked to transform it into a singly linked list in-place such that the linked list follows the preorder traversal of the tree. Which approach guarantees an optimal solution with O(n) time and O(h) space complexity, where h is the tree height?

easy

A. Use a reverse preorder traversal (right subtree first, then left) with a global pointer to rewire nodes in-place.

B. Perform a preorder traversal, store nodes in a list, then rebuild the linked list from the list.

C. Use a bottom-up postorder traversal to reconstruct the linked list from leaves to root.

D. Apply a greedy approach that always attaches the left subtree to the rightmost node of the right subtree.

Solution

1. Step 1: Understand traversal order needed

   The linked list must follow preorder traversal (root, left, right).

2. Step 2: Identify approach that rewires in-place efficiently

   Reverse preorder traversal (right, left) with a global pointer allows rewiring nodes in-place without extra storage, achieving O(n) time and O(h) space due to recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reverse preorder traversal with global pointer rewires nodes in correct order [OK]

Hint: Reverse preorder traversal with global pointer is optimal [OK]

Common Mistakes:

• Using extra space to store nodes before rebuilding
• Confusing traversal order causing incorrect linked list
• Trying greedy rewiring without correct traversal order

3. Consider the following code snippet implementing the parent pointer + ancestor set approach for Lowest Common Ancestor. Given the tree below and nodes p=5 and q=1, what is the final returned node's value? Tree structure: 3 / \ 5 1 / \ \ 6 2 8

def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

easy

A. 3

B. 5

C. 1

D. 2

Solution

1. Step 1: Trace parent map construction

   Stack starts with root=3. Pop 3, add children 5 and 1 with parent 3. Pop 1, add child 8 with parent 1. Pop 8 (no children). Pop 5, add children 6 and 2 with parent 5. Parent map built for all nodes.

2. Step 2: Trace ancestor sets and final return

   Ancestors of p=5 are {5,3,None}. For q=1, check if in ancestors: 1 not in {5,3}, move to parent 3 which is in ancestors. Return 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root 3 is LCA of 5 and 1 in given tree [OK]

Hint: LCA of sibling subtrees is their parent [OK]

Common Mistakes:

• Returning p or q directly
• Confusing parent pointers
• Off-by-one in ancestor check

4. What is the time complexity of the optimal iterative postorder traversal algorithm for computing the maximum path sum in a binary tree with n nodes and height h?

medium

A. O(n) because each node is visited a constant number of times

B. O(n log n) due to repeated subtree computations

C. O(h * n) because the stack operations depend on tree height

D. O(n^2) in worst case due to nested traversal of subtrees

Solution

1. Step 1: Identify node visits

   Each node is pushed and popped from the stack once, and gains are computed once per node.

2. Step 2: Analyze stack operations and computations

   Stack size is at most h, but operations per node are constant, so total time is proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time traversal with constant work per node [OK]

Hint: Each node processed once, O(n) time [OK]

Common Mistakes:

• Confusing stack height with repeated visits
• Assuming nested loops cause O(n^2)
• Thinking recursion stack adds multiplicative factor

5. The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.

from collections import deque

def maxDepth(root):
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

medium

A. Line 7: Using len(queue) to determine level size

B. Line 15: Incrementing depth after processing each level

C. Line 10: Popping node from queue without null check

D. Line 2: Initializing queue with root without checking if root is null

Solution

1. Step 1: Check handling of empty tree

   Code initializes queue with root without checking if root is null, so if root is null, queue contains null, causing errors.

2. Step 2: Verify other lines

   len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing root null check causes failure on empty tree [OK]

Hint: Always check for null root before queue initialization [OK]

Common Mistakes:

• Not handling empty tree input
• Assuming root always exists
• Incrementing depth incorrectly