Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoft

Binary Tree Postorder Traversal

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"root":[1,null,2,3]}
Expected[3,2,1]

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

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

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).

t2_01edge
Input{"root":null}
Expected[]

Empty tree returns empty list.

t2_02edge
Input{"root":[7]}
Expected[7]

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

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

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

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

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

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

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

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

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

t4_01performance
Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?
easy
A. Use a breadth-first search (BFS) to visit nodes level by level.
B. Use a recursive preorder traversal that visits root, left, then right nodes.
C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.
D. Use a dynamic programming approach to store and reuse subtree results.

Solution

  1. Step 1: Understand traversal order requirement

    Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
  2. Step 2: Identify approach with O(1) space

    Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Morris traversal is known for O(1) space inorder traversal [OK]
Hint: Morris traversal enables inorder with O(1) space [OK]
Common Mistakes:
  • Confusing preorder with inorder traversal order
  • Assuming BFS can produce inorder sequence
  • Thinking DP applies to traversal order
2. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?
easy
A. Postorder traversal using two stacks
B. Level-order traversal using a queue
C. Morris preorder traversal using threaded binary tree
D. Inorder traversal using recursion

Solution

  1. Step 1: Understand traversal order requirement

    The problem requires visiting root before left and right subtrees, which is preorder traversal.
  2. Step 2: Identify approach with no extra space

    Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
Hint: Preorder visits root before children [OK]
Common Mistakes:
  • Confusing inorder or postorder with preorder traversal
  • Assuming recursion is always needed
  • Using level-order which visits nodes by depth
3. Consider the following BFS-based Python code to compute the maximum depth of a binary tree. Given the tree below, what is the value of depth after the second iteration of the while loop? Tree structure: - Root node 1 - Left child 2 - Right child 3 - Left child of 2 is 4
from collections import deque

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

def maxDepth(root):
    if root is None:
        return 0
    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

root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(maxDepth(root))
easy
A. 1
B. 2
C. 3
D. 4

Solution

  1. Step 1: Trace first iteration of while loop

    Initially, queue contains root (1). level_size=1. After processing node 1, enqueue its children 2 and 3. Increment depth to 1.
  2. Step 2: Trace second iteration of while loop

    Queue now has nodes 2 and 3. level_size=2. Process node 2 (enqueue 4), process node 3 (no children). Increment depth to 2.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Depth increments after each level processed; after second level depth=2 [OK]
Hint: Depth increments after processing each tree level [OK]
Common Mistakes:
  • Counting nodes instead of levels
  • Off-by-one in depth increment
  • Ignoring children enqueueing
4. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?
hard
A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.
B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.
C. Switch to preorder and inorder traversals which do not have duplicates.
D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

  1. Step 1: Understand the impact of duplicates

    Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.
  2. Step 2: Required modification

    Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.
  3. Step 3: Why other options fail

    Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking multiple indices per value is necessary for duplicates [OK]
Hint: Duplicates require tracking all indices, not just one [OK]
Common Mistakes:
  • Ignoring duplicates in hash map
  • Assuming unique values always
  • Switching traversal types incorrectly
5. Suppose the binary tree nodes can have negative values and you want to find the diameter defined as the longest path in terms of number of edges (ignoring node values). Which modification to the standard diameter algorithm is necessary to handle this variant correctly?
hard
A. No modification needed; the standard diameter algorithm based on heights works regardless of node values.
B. Modify the algorithm to sum node values along paths and find maximum sum path instead of longest path.
C. Change the height calculation to ignore negative nodes by treating them as null nodes.
D. Use breadth-first search to find the longest path instead of depth-first traversal.

Solution

  1. Step 1: Recognize diameter depends on path length (edges), not node values.

    Negative values do not affect height or path length calculations.
  2. Step 2: Confirm standard height-based diameter algorithm works unchanged.

    Heights and diameter calculations rely on structure, so no changes are needed.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Diameter depends on edges, not node values [OK]
Hint: Diameter is structural, unaffected by node values [OK]
Common Mistakes:
  • Confusing diameter with max sum path
  • Ignoring negative nodes incorrectly
  • Switching to BFS unnecessarily
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard