Binary Tree Preorder Traversal

📋

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
}

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

Handle base cases like empty tree and single node correctly.

Check traversal order carefully; left subtree must come before right.

Optimize your solution to run in linear time for large trees.

t1_01basic

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

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

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.

💡 Preorder traversal visits root before children.

💡 Visit root, then recursively traverse left subtree, then right subtree.

💡 Return list combining root value + preorder(left) + preorder(right).

Why it failed: Output order incorrect: likely not visiting root first or mixing left/right order. Fix by ensuring root.val is added before recursive calls.

✓ Correct preorder traversal order confirmed.

t1_02basic

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

Expected[4,5,6]

⏱ Performance - must finish in 2000ms

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

💡 Remember preorder is root, left, right.

💡 Check that left subtree is fully traversed before right subtree.

💡 Combine root value with preorder of left and right children in order.

Why it failed: Traversal order wrong: possibly swapped left and right subtree traversal. Fix by visiting left subtree before right subtree.

✓ Traversal order matches preorder definition.

t2_01edge

Input{"root":null}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree returns empty list.

💡 Check for null root as base case.

💡 Return empty list if root is null.

💡 Add condition: if root is null, return [].

Why it failed: Function crashes or returns non-empty for null root. Fix by adding base case returning empty list when root is null.

✓ Correctly handles empty tree input.

t2_02edge

Input{"root":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

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

💡 Preorder of single node is just that node's value.

💡 Ensure function returns list with root.val when no children.

💡 Return [root.val] if root.left and root.right are null.

Why it failed: Output empty or incorrect for single node. Fix by returning list with root.val when no children.

✓ Correctly returns single node value.

t2_03edge

Input{"root":[8,9,null,10]}

Expected[8,9,10]

⏱ Performance - must finish in 2000ms

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

💡 Preorder visits root then left subtree fully.

💡 Check recursive calls correctly traverse left children.

💡 Return [8] + preorder(left subtree) + preorder(null).

Why it failed: Left subtree traversal missing or reversed. Fix by recursively traversing left child before right.

✓ Correct preorder traversal of left-only tree.

t3_01corner

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

Expected[11,12,13]

⏱ Performance - must finish in 2000ms

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

💡 Preorder visits root then left then right.

💡 Check that left subtree traversal returns empty list if null.

💡 Return [root.val] + preorder(left) + preorder(right).

Why it failed: Incorrect order due to treating right child as left or skipping right subtree. Fix by correctly traversing right subtree after left.

✓ Correct preorder traversal of right-only tree.

t3_02corner

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

Expected[14,15,16]

⏱ Performance - must finish in 2000ms

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

💡 Preorder visits root, then left subtree fully, then right subtree.

💡 Ensure recursive call on left subtree includes its right child.

💡 Return [14] + preorder(left subtree) + preorder(null).

Why it failed: Missing right child of left subtree in traversal. Fix by recursively traversing both left and right children of each node.

✓ Correct preorder traversal including nested right child.

t3_03corner

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

Expected[17,18,19]

⏱ Performance - must finish in 2000ms

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

💡 Preorder is root, left, right - order matters.

💡 Check traversal order carefully to avoid swapping left and right.

💡 Return [root.val] + preorder(left) + preorder(right), not reversed.

Why it failed: Swapped left and right subtree traversal order. Fix by ensuring left subtree is traversed before right subtree.

✓ Correct preorder traversal order with left before right.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Preorder traversal is O(n) time complexity.

💡 Recursive or iterative stack-based traversal should be efficient.

💡 Avoid exponential or repeated work to prevent TLE.

Why it failed: TLE due to exponential or repeated traversal calls. Fix by using O(n) traversal visiting each node once.

✓ Traversal completes in linear time as expected.

Practice

1. Consider the following Python code implementing the optimal flatten function for a binary tree. Given the input tree: 1 / \ 2 3 What is the value of the global variable prev after the call flatten(root) completes?

easy

A. TreeNode with val=3

B. TreeNode with val=1

C. TreeNode with val=2

D. None

Solution

1. Step 1: Trace flatten calls on root=1

   flatten(1) calls flatten(3) then flatten(2). After flatten(3), prev=TreeNode with val=3; after flatten(2), prev=TreeNode with val=2; finally, root=1 sets root.right=prev (2) and prev=TreeNode with val=1.

2. Step 2: Final value of prev after flatten(1)

   After processing root=1, prev points to the root node with val=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Global prev ends at root node after full traversal [OK]

Hint: Global prev ends at root after full flatten [OK]

Common Mistakes:

• Assuming prev ends at last leaf node
• Confusing order of recursive calls
• Forgetting prev is updated after rewiring

2. What is the time complexity of the optimized iterative approach using a stack and a hash map to build a binary tree from preorder and inorder traversals of length n?

medium

A. O(n^2) due to nested loops scanning preorder and inorder arrays

B. O(n log n) due to hash map lookups for inorder indices

C. O(n) because each node is pushed and popped at most once from the stack

D. O(n) but with O(n^2) auxiliary space for recursion stack

Solution

1. Step 1: Analyze main loops

   The algorithm iterates preorder once, pushing and popping nodes from stack at most once each.

2. Step 2: Consider hash map lookups

   Hash map lookups for inorder indices are O(1) each, so no extra log factor.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each node processed once with O(1) operations [OK]

Hint: Each node pushed and popped once; hash map lookups O(1) [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing hash map lookup cost
• Counting recursion stack space in iterative approach

3. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity

4. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?

hard

A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.

B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.

C. Switch to preorder traversal without null markers to reduce string size and recursion depth.

D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

1. Step 1: Identify problem with deep recursion

   Recursive DFS can cause stack overflow on very deep trees.

2. Step 2: Use iterative BFS with null markers

   Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.

3. Step 3: Avoid assumptions about uniqueness or balanced shape

   Duplicates require storing all nodes explicitly; balanced assumptions break correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Iterative BFS with null markers handles deep trees and duplicates safely [OK]

Hint: Iterative BFS avoids recursion limits and preserves structure [OK]

Common Mistakes:

• Removing null markers to save space breaks reconstruction
• Using recursion on deep trees causes stack overflow
• Assuming unique values or balanced trees

5. Suppose the problem is extended: the tree nodes can have duplicate values, and you want to check if the tree is symmetric ignoring node values, only structure matters. Which modification to the original DFS approach correctly solves this variant?

hard

A. Keep the value comparison but add a hash map to track visited nodes to avoid duplicates.

B. Use BFS level-order traversal and check if each level forms a palindrome of node values.

C. Modify the base case to return true if both nodes are null, and skip the value comparison step entirely.

D. Perform a preorder traversal and compare the traversal list with its reverse.

Solution

1. Step 1: Understand the variant ignores node values, only structure matters

   Therefore, the value comparison step must be removed to avoid false negatives due to duplicates.

2. Step 2: Modify the DFS to only check if both nodes exist or are null, recursively comparing mirrored subtrees

   Return true if both nodes are null; otherwise, recurse on mirrored children without comparing values.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ignoring values means skipping value checks but preserving mirrored structure checks [OK]

Hint: Ignore values, check only mirrored structure recursively [OK]

Common Mistakes:

• Keeping value checks causing false negatives
• Using BFS palindrome checks which fail on structure
• Using preorder traversal which ignores mirrored structure