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 are given two arrays representing the preorder and inorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant subtree searches?

easy

A. Use breadth-first search to build the tree level by level from preorder and inorder arrays.

B. Use a greedy approach that picks nodes based on preorder and attaches them arbitrarily to the left or right.

C. Use dynamic programming to store subtree results and combine them for the full tree.

D. Use recursion with a hash map to quickly find root indices in inorder traversal, avoiding repeated searches.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a binary tree from preorder and inorder requires knowing root positions quickly to split subtrees.

2. Step 2: Identify the optimal approach

   Using a hash map for inorder indices allows O(1) root lookups, avoiding repeated O(n) searches in recursion.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map lookup avoids repeated scanning [OK]

Hint: Hash map lookup avoids repeated inorder searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree correctly
• Confusing DP with tree construction
• Ignoring the need for quick root index lookup

3. Given the following code snippet for building a binary tree from preorder and inorder traversals, what is the value of inorder_index after processing the second element of preorder = [3,9,20] and inorder = [9,3,20]?

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Initialize variables

   Start with root=3, stack=[3], inorder_index=0 (inorder[0]=9).

2. Step 2: Process second preorder element (9)

   Top of stack is 3, which is not equal to inorder[0]=9, so 9 becomes left child of 3 and is pushed to stack. inorder_index remains 0.

3. Step 3: Process third preorder element (20)

   Top of stack is 9, which equals inorder[0]=9, so pop 9 and increment inorder_index to 1. Now top is 3, equals inorder[1]=3, pop 3 and increment inorder_index to 2. Then 20 becomes right child of 3 and is pushed to stack.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   inorder_index increments twice after processing 20, so after second element it is 1 [OK]

Hint: inorder_index increments only when stack top matches inorder element [OK]

Common Mistakes:

• Off-by-one increment of inorder_index
• Confusing preorder and inorder indices
• Forgetting to pop stack before incrementing inorder_index

4. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.

B. Use dynamic programming to store sums of subtrees and combine results bottom-up.

C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.

D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

1. Step 1: Understand problem constraints and path definition

   The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.

2. Step 2: Recognize prefix sum with DFS pattern

   Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prefix sum + DFS solves in linear time [OK]

Hint: Prefix sums track cumulative sums efficiently [OK]

Common Mistakes:

• Assuming paths must start at root or leaf
• Using brute force DFS from every node without pruning
• Trying greedy pruning which fails on negative values

5. Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                # Bug here
                current = current.right
    return result

medium

A. Line resetting predecessor.right to None is missing in the else block

B. Appending current.val before moving to left child is incorrect

C. The inner while loop condition should check predecessor.left instead of predecessor.right

D. The check for current.left being None should be after the else block

Solution

1. Step 1: Identify missing restoration of tree structure

   In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.

2. Step 2: Locate missing line

   The else block lacks the line predecessor.right = None, causing the threaded link to persist.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without resetting, tree remains modified after traversal [OK]

Hint: Always reset threaded links to None after use [OK]

Common Mistakes:

• Forgetting to restore tree structure
• Appending nodes in wrong order
• Incorrect loop conditions