Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoft

Binary Tree Preorder Traversal

Choose your preparation mode4 modes available
📋
Problem

Imagine you are building a file explorer that needs to list folders and files in a specific order starting from the root folder, visiting each folder before its contents.

Given the root of a binary tree, return the preorder traversal of its nodes' values. Preorder traversal visits nodes in the order: root, left subtree, right subtree.

The number of nodes in the tree is in the range [1, 10^5].-10^5 <= Node.val <= 10^5
Edge cases: Single node tree → output is the single node valueTree with only left children → output is nodes from top to bottomTree with only right children → output is nodes from top to bottom
</>
IDE
def preorderTraversal(root: Optional[TreeNode]) -> List[int]:public List<Integer> preorderTraversal(TreeNode root)vector<int> preorderTraversal(TreeNode* root)function preorderTraversal(root)
def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    # Write your solution here
    pass
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}
#include <vector>
using namespace std;

vector<int> preorderTraversal(TreeNode* root) {
    // Write your solution here
    return {};
}
function preorderTraversal(root) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [2, 3, 1]Returning postorder or incorrect traversal order (left-right-root instead of root-left-right).✅ Change traversal order to add root value before recursive calls to left and right children.
Wrong: [1, 3, 2]Swapping left and right subtree traversal order.✅ Ensure preorder visits left subtree before right subtree: preorder(root.left) then preorder(root.right).
Wrong: [1]Not traversing children nodes or missing recursive calls.✅ Add recursive calls to both left and right children and concatenate their results.
Wrong: Exception or crashNot handling null root input properly.✅ Add base case: if root is null, return empty list.
Wrong: Timeout or no outputInefficient traversal causing exponential time complexity.✅ Use O(n) traversal visiting each node once, avoid repeated calls.
✓
Test Cases
t1_01basic
Input{"root":[1,null,2,3]}
Expected[1,2,3]

Start at root (1), then left subtree (null), then right child (2), then left child of 2 (3). Preorder visits root, then left, then right.

t1_02basic
Input{"root":[4,5,6]}
Expected[4,5,6]

Root 4, then left child 5, then right child 6.

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":[8,9,null,10]}
Expected[8,9,10]

Tree with only left children: preorder visits top to bottom left.

t3_01corner
Input{"root":[11,null,12,null,13]}
Expected[11,12,13]

Tree with only right children: preorder visits top to bottom right.

t3_02corner
Input{"root":[14,15,null,null,16]}
Expected[14,15,16]

Tree where left child has right child: preorder must visit left child before its right child.

t3_03corner
Input{"root":[17,18,19]}
Expected[17,18,19]

Common greedy trap: visiting right child before left child breaks preorder.

t4_01performance
Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}
⏱ Performance - must finish in 2000ms

Deep left-skewed tree with n=100 nodes; O(n) traversal must complete within 2 seconds.

Practice

(1/5)
1. 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
2. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?
easy
A. Use a greedy approach by always attaching nodes as left children when possible.
B. Use dynamic programming to store subtrees and avoid recomputation.
C. Use recursion with a hash map to quickly find root indices in the inorder array.
D. Use breadth-first search to reconstruct the tree level by level.

Solution

  1. Step 1: Understand the problem constraints

    Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.
  2. Step 2: Evaluate approaches

    Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Hash map lookup avoids O(n) search per recursion [OK]
Hint: Hash map lookup avoids repeated linear searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree uniquely
  • Confusing DP with tree construction
  • Ignoring index lookup cost
3. Consider the following code implementing the optimal House Robber III solution. Given the tree: 3 / \ 2 3 \ \ 3 1 What is the value of rob_current when dfs is called on the root node (value 3)?
easy
A. 7
B. 6
C. 8
D. 9

Solution

  1. Step 1: Trace dfs on left child (value 2)

    dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).
  2. Step 2: Trace dfs on right child (value 3)

    dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).
  3. Step 3: Calculate rob_current at root (value 3)

    rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Sum matches known example output 7 [OK]
Hint: Add node.val + not_rob of children for rob_current [OK]
Common Mistakes:
  • Mixing rob and not_rob values for children
  • Off-by-one in recursion returns
4. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?
easy
A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.
B. Perform a level-order traversal and compare nodes at each level from left to right.
C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.
D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

  1. Step 1: Understand the problem requires mirrored subtree comparison

    The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.
  2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

    The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Mirrored recursive DFS matches problem requirements [OK]
Hint: Symmetry requires mirrored subtree comparison [OK]
Common Mistakes:
  • Assuming preorder traversal palindrome check works
  • Using level-order traversal without mirrored comparison
  • Trying brute force subtree permutations
5. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.
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
medium
A. Line: while p not in parent or q not in parent:
B. Line: while p:
C. Line: while q not in ancestors:
D. Line: parent = {root: None}

Solution

  1. Step 1: Analyze parent map construction loop

    The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.
  2. Step 2: Identify subtle bug

    If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.
  3. Step 3: Explanation

    The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Loop condition must ensure both nodes are in parent map to avoid errors [OK]
Hint: Parent map construction loop must fully process both nodes [OK]
Common Mistakes:
  • Assuming parent map always complete
  • Ignoring incomplete parent map causing KeyError
  • Misplacing bug in ancestor set loops
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