Binary Tree Postorder Traversal

📋

Problem

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.

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

Edge cases: Single node tree → output is the node itselfTree with only left children → output is nodes from bottom to topTree with only right children → output is nodes from bottom to top

</>

IDE

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:public List<Integer> postorderTraversal(TreeNode root)vector<int> postorderTraversal(TreeNode* root)function postorderTraversal(root)

def postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    # Write your solution here
    pass

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> postorderTraversal(TreeNode* root) {
    // Write your solution here
    return {};
}

function postorderTraversal(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 3, 2]Preorder traversal output instead of postorder; node appended before children.✅ Append node value after recursive calls to left and right children, not before.

Wrong: [2, 1]Missing left subtree nodes in traversal due to incorrect recursion or iteration.✅ Ensure recursion or iteration visits left child before appending node.

Wrong: []Returning empty list for non-empty tree due to missing base case or incorrect recursion.✅ Add base case to append node value when node is not null and has no children.

Wrong: Runtime error or crashNull pointer dereference due to missing null checks in recursion or iteration.✅ Check if node is null before accessing its children or value.

Wrong: Timeout or TLEInefficient traversal with repeated visits or exponential complexity.✅ Implement O(n) traversal visiting each node once using recursion or iterative stack.

✓

Test Cases

Handle empty and minimal trees carefully to avoid null pointer errors.

Focus on traversal order and handling missing children correctly.

Optimize your solution to linear time and space complexity.

t1_01basic

Input{"root":[1,null,2,3]}

Expected[3,2,1]

⏱ Performance - must finish in 2000ms

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

💡 Postorder traversal visits left subtree, then right subtree, then the node itself.

💡 Use recursion or stack to ensure left and right children are processed before the node.

💡 Append node value after traversing left and right children.

Why it failed: Output order incorrect: likely visiting root before children or missing left subtree. Fix by ensuring node.val is appended after left and right recursive calls.

✓ Correct postorder traversal order confirmed.

t1_02basic

Input{"root":[4,2,5,1,3]}

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

⏱ Performance - must finish in 2000ms

Tree: root 4 with left subtree 2 (children 1 and 3) and right child 5. Postorder: left subtree (1,3,2), right subtree (5), root (4).

💡 Traverse left subtree completely before right subtree.

💡 Use recursion or stack to process children before node.

💡 Append node value after processing both children.

Why it failed: Incorrect output order: possibly visiting root before children or skipping subtrees. Fix by appending node value after left and right traversals.

✓ Postorder traversal logic correctly implemented.

t2_01edge

Input{"root":null}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree returns empty list.

💡 Check for null root before traversal.

💡 Return empty list if root is null.

💡 Avoid accessing properties of null nodes.

Why it failed: Code crashes or returns non-empty for null root. Fix by adding base case: if root is null, return empty list immediately.

✓ Handles empty tree correctly.

t2_02edge

Input{"root":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

Single node tree returns list with that node's value.

💡 Postorder of single node is the node itself.

💡 Ensure base case returns node value when no children.

💡 No recursion needed beyond root if no children.

Why it failed: Output empty or missing node value for single node tree. Fix by appending node.val when node has no children.

✓ Single node tree handled correctly.

t2_03edge

Input{"root":[1,2,null,3,null,4]}

Expected[4,3,2,1]

⏱ Performance - must finish in 2000ms

Tree with only left children: 1 -> 2 -> 3 -> 4. Postorder visits bottom to top left nodes.

💡 Traverse left subtree fully before right subtree.

💡 Ensure recursion or stack handles left children correctly.

💡 Append node after left and right children.

Why it failed: Output order incorrect or missing left children. Fix by correctly recursing down left subtree before appending node.

✓ Left-child-only tree postorder correct.

t3_01corner

Input{"root":[1,null,2,null,3]}

Expected[3,2,1]

⏱ Performance - must finish in 2000ms

Tree with only right children: 1 -> 2 -> 3. Postorder visits bottom to top right nodes.

💡 Postorder visits left then right subtree before node.

💡 Check that right children are not skipped.

💡 Append node after both children processed.

Why it failed: Output missing right children or wrong order. Fix by ensuring right subtree is traversed before appending node.

✓ Right-child-only tree postorder correct.

t3_02corner

Input{"root":[1,2,3,4,5,6,7]}

Expected[4,5,2,6,7,3,1]

⏱ Performance - must finish in 2000ms

Complete binary tree with 7 nodes. Postorder visits left subtree (4,5,2), right subtree (6,7,3), then root (1).

💡 Do not confuse preorder with postorder traversal.

💡 Postorder appends node after left and right children.

💡 Check recursion or stack order carefully.

Why it failed: Output matches preorder or inorder traversal. Fix by appending node after left and right children, not before.

✓ Correct postorder traversal of complete tree.

t3_03corner

Input{"root":[1,2,3,null,4,5]}

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

⏱ Performance - must finish in 2000ms

Tree with mixed missing children. Postorder visits left subtree (4,2), right subtree (5,3), then root (1).

💡 Handle null children correctly in recursion or iteration.

💡 Ensure left and right children are processed even if one is missing.

💡 Append node after children.

Why it failed: Output missing nodes or wrong order due to null child mishandling. Fix by checking for null before recursion and appending node last.

✓ Handles trees with missing children correctly.

t4_01performance

Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10]}

Expectednull

⏱ Performance - must finish in 2000ms

Deep left-skewed tree with 10 nodes to test performance of O(n) traversal within 2 seconds.

💡 Postorder traversal is O(n) time and space.

💡 Use iterative or recursive approach with O(n) complexity.

💡 Avoid exponential or repeated work to prevent TLE.

Why it failed: Solution exceeds time limit due to non-linear complexity or repeated traversals. Fix by implementing O(n) traversal visiting each node once.

✓ Traversal completes in linear time as expected.

Practice

1. You need to determine if a binary tree is height-balanced, meaning the heights of the two child subtrees of any node never differ by more than one. Which approach guarantees an optimal O(n) time solution without redundant height computations?

easy

A. Use a top-down recursive approach that checks balance only at the root node.

B. Compute height for each node separately and check balance at each node recursively.

C. Perform a breadth-first traversal and check balance by comparing subtree sizes at each level.

D. Use a postorder traversal that returns height and balance status simultaneously, stopping early if imbalance is found.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking balance at every node efficiently without recomputing heights multiple times.

2. Step 2: Identify the approach that avoids redundant work

   Postorder traversal that returns both height and balance status in one pass allows early exit on imbalance and avoids repeated height calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Postorder traversal with early exit is O(n) and avoids recomputation [OK]

Hint: Postorder traversal with early exit avoids repeated height calls [OK]

Common Mistakes:

• Checking balance only at root misses subtree imbalances
• Computing height separately for each node causes O(n²) time
• Using BFS to check balance is incorrect as balance depends on subtree heights

2. You need to place the minimum number of cameras in a binary tree so that every node is monitored. A camera at a node monitors its parent, itself, and its immediate children. Which approach guarantees an optimal solution for this problem?

easy

A. Brute force recursion trying all combinations of camera placements

B. Greedy postorder traversal using explicit states to track coverage and camera placement

C. Top-down dynamic programming with memoization based on node coverage

D. Level order traversal placing cameras on all nodes with uncovered children

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal cameras covering all nodes, where a camera covers parent, self, and children.

2. Step 2: Evaluate approaches

   Brute force is exponential and inefficient. Level order placing cameras on all uncovered children is greedy but not minimal. Top-down DP is complex and less intuitive here. Greedy postorder with explicit states ensures children are processed before parent decisions, enabling minimal camera placement.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Postorder traversal with states is known optimal for this problem [OK]

Hint: Optimal solution uses postorder traversal with states [OK]

Common Mistakes:

• Assuming level order greedy placement is minimal
• Trying brute force without pruning
• Confusing top-down DP with bottom-up greedy

3. What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because each node is visited multiple times during threading

B. O(n) but with O(n) auxiliary space due to recursion stack

C. O(n^2) because the inner loop to find predecessor can traverse many nodes repeatedly

D. O(n) because each edge is traversed at most twice during threading and restoration

Solution

1. Step 1: Identify traversal of nodes and edges

   Each node is visited once, and each edge is traversed at most twice (once to create thread, once to remove it).

2. Step 2: Explain why complexity is linear

   Because total edge traversals sum to O(n), the overall time complexity is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Threading and restoring links cause at most two visits per edge [OK]

Hint: Each edge visited max twice -> O(n) time [OK]

Common Mistakes:

• Assuming inner loop causes O(n^2)
• Confusing threading with recursion stack space
• Thinking threading causes log n overhead

4. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

medium

A. Line with 'if not node:' return statement

B. Line adding current_number to self.total

C. Line checking if node is leaf

D. Line calling dfs on node.right

Solution

1. Step 1: Understand when sums should be added

   Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.

2. Step 2: Identify incorrect addition

   Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum only at leaves fixes the bug [OK]

Hint: Add to total only at leaf nodes [OK]

Common Mistakes:

• Adding partial path sums at non-leaf nodes
• Not resetting total between calls

5. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?

hard

A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting

B. Use recursion on parent pointers to simulate traversal

C. Iteratively traverse using parent pointers and a stack to track visited nodes

D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

1. Step 1: Understand traversal constraints

   Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.

2. Step 2: Identify correct approach

   Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modified iterative approach handles parent-only trees without extra space [OK]

Hint: Parent-only trees require tracking visited nodes iteratively [OK]

Common Mistakes:

• Trying to use recursion without child pointers
• Attempting Morris traversal on parent pointers
• Using stack without tracking visited nodes