Binary Tree Preorder Traversal

🎯

Binary Tree Preorder Traversal

easyTREEAmazonMicrosoft

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.

💡 This problem is about traversing a binary tree in preorder, which means visiting the root node first, then recursively visiting the left subtree, followed by the right subtree. Beginners often struggle with understanding the traversal order and implementing it both recursively and iteratively.

📋

Problem Statement

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

💡

Example

Input"root = [1,null,2,3]"

Output[1,2,3]

Start at root (1), then right child (2), then left child of 2 (3).

• Single node tree → output is the single node value
• Tree with only left children → output is nodes from top to bottom
• Tree with only right children → output is nodes from top to bottom
• Empty tree (root = null) → output is an empty list

⚠️

Common Mistakes

Visiting nodes in wrong order (e.g., left before root)

Output does not match preorder traversal order

✅ Ensure root is visited before left and right children

Forgetting to check for null nodes before recursion or stack push

Runtime errors or null pointer exceptions

✅ Always check if node is null before processing

Pushing left child before right child in iterative approach

Traversal order becomes incorrect (right subtree visited before left)

✅ Push right child first, then left child to stack

Not restoring tree structure in Morris traversal

Tree remains modified after traversal, causing side effects

✅ Remove temporary threads after use by setting predecessor.right to null

Using recursion without considering stack overflow for deep trees

Stack overflow error on very deep or skewed trees

✅ Use iterative approach or Morris traversal for large/deep trees

🧠

Brute Force (Pure Recursion)

💡 Starting with recursion helps understand the natural definition of preorder traversal and builds intuition before optimizing or switching to iterative methods.

Intuition

Preorder traversal means visiting the root node first, then recursively traversing the left subtree, followed by the right subtree. Recursion naturally fits this definition by calling the function on subtrees.

Algorithm

1. Visit the current node and record its value.
2. Recursively traverse the left subtree in preorder.
3. Recursively traverse the right subtree in preorder.
4. Combine the results to form the preorder traversal list.

💡 The recursion stack implicitly keeps track of nodes to visit next, which can be tricky to visualize at first.

</>

Code

from typing import Optional, List

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

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)

# Example usage:
# Construct tree: 1
#                 \ 
#                  2
#                 / 
#                3
# root = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
# print(preorderTraversal(root))  # Output: [1, 2, 3]

Line Notes

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:Defines the function signature with type hints for clarity.

if root is None:Base case: if the current node is null, return an empty list to stop recursion.

return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)Visit root first, then recursively traverse left and right subtrees, concatenating results.

class TreeNode:Defines the binary tree node structure used in the problem.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.right = new TreeNode(2);
    //     root.right.left = new TreeNode(3);
    //     Solution sol = new Solution();
    //     System.out.println(sol.preorderTraversal(root)); // Output: [1, 2, 3]
    // }
}

Line Notes

public List<Integer> preorderTraversal(TreeNode root) {Method signature returning a list of integers representing preorder traversal.

if (root == null) return result;Base case: return empty list if node is null to end recursion.

result.add(root.val);Visit the root node first and add its value to the result list.

result.addAll(preorderTraversal(root.left));Recursively traverse the left subtree and add all its values.

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> preorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> res = {root->val};
    vector<int> left = preorderTraversal(root->left);
    vector<int> right = preorderTraversal(root->right);
    res.insert(res.end(), left.begin(), left.end());
    res.insert(res.end(), right.begin(), right.end());
    return res;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->right = new TreeNode(2);
//     root->right->left = new TreeNode(3);
//     vector<int> result = preorderTraversal(root);
//     for (int val : result) cout << val << ' ';
//     cout << endl; // Output: 1 2 3
//     return 0;
// }

Line Notes

vector<int> preorderTraversal(TreeNode* root) {Function returns a vector of integers representing preorder traversal.

if (!root) return {};Base case: return empty vector if node is null to stop recursion.

vector<int> res = {root->val};Start result vector with current node's value.

res.insert(res.end(), left.begin(), left.end());Append preorder traversal of left subtree to result.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function preorderTraversal(root) {
    if (root === null) return [];
    return [root.val].concat(preorderTraversal(root.left), preorderTraversal(root.right));
}

// Example usage:
// const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
// console.log(preorderTraversal(root)); // Output: [1, 2, 3]

Line Notes

function preorderTraversal(root) {Defines the preorder traversal function.

if (root === null) return [];Base case: return empty array if node is null.

return [root.val].concat(preorderTraversal(root.left), preorderTraversal(root.right));Visit root, then recursively traverse left and right subtrees, concatenating results.

function TreeNode(val, left = null, right = null) {Defines the TreeNode constructor function.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited exactly once, so time is O(n). The recursion stack can go as deep as the height of the tree, which in worst case is O(n).

💡 For a tree with 20 nodes, this means about 20 function calls and 20 visits, which is efficient for interview standards.

Interview Verdict: Accepted

This approach is accepted and often the first step in interviews to demonstrate understanding of tree traversal.

🧠

Iterative Approach Using Stack

💡 Iterative traversal avoids recursion stack overflow and is often preferred in production code. It also demonstrates understanding of how recursion can be simulated with a stack.

Intuition

Use a stack to simulate the call stack of recursion. Push the root node first, then process nodes by popping from the stack, pushing right child first and then left child to ensure left subtree is processed before right.

Algorithm

1. Initialize a stack and push the root node if not null.
2. While the stack is not empty, pop the top node and record its value.
3. Push the right child of the popped node if it exists.
4. Push the left child of the popped node if it exists.
5. Repeat until stack is empty.

💡 The order of pushing right then left child ensures left subtree is processed first, matching preorder traversal order.

</>

Code

from typing import Optional, List

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

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    stack, output = [root], []
    while stack:
        node = stack.pop()
        output.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return output

# Example usage:
# root = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
# print(preorderTraversal(root))  # Output: [1, 2, 3]

Line Notes

stack, output = [root], []Initialize stack with root to start traversal and output list to store results.

while stack:Loop until all nodes are processed.

node = stack.pop()Pop the current node to process it.

if node.right: stack.append(node.right)Push right child first so left child is processed first.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.right = new TreeNode(2);
    //     root.right.left = new TreeNode(3);
    //     Solution sol = new Solution();
    //     System.out.println(sol.preorderTraversal(root)); // Output: [1, 2, 3]
    // }
}

Line Notes

Deque<TreeNode> stack = new ArrayDeque<>();Use Deque as a stack for efficient push/pop operations.

stack.push(root);Start traversal by pushing root node onto stack.

while (!stack.isEmpty()) {Process nodes until stack is empty.

if (node.right != null) stack.push(node.right);Push right child first to ensure left child is processed first.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        res.push_back(node->val);
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
    return res;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->right = new TreeNode(2);
//     root->right->left = new TreeNode(3);
//     vector<int> result = preorderTraversal(root);
//     for (int val : result) cout << val << ' ';
//     cout << endl; // Output: 1 2 3
//     return 0;
// }

Line Notes

stack<TreeNode*> stk;Declare a stack to hold nodes for iterative traversal.

stk.push(root);Push root node to start traversal.

while (!stk.empty()) {Loop until all nodes are processed.

if (node->right) stk.push(node->right);Push right child first to process left child first.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function preorderTraversal(root) {
    if (root === null) return [];
    const stack = [root];
    const output = [];
    while (stack.length > 0) {
        const node = stack.pop();
        output.push(node.val);
        if (node.right !== null) stack.push(node.right);
        if (node.left !== null) stack.push(node.left);
    }
    return output;
}

// Example usage:
// const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
// console.log(preorderTraversal(root)); // Output: [1, 2, 3]

Line Notes

const stack = [root];Initialize stack with root node to start traversal.

while (stack.length > 0) {Process nodes until stack is empty.

const node = stack.pop();Pop the top node to process it.

if (node.right !== null) stack.push(node.right);Push right child first to ensure left child is processed first.

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is pushed and popped once, so time is O(n). The stack can hold up to O(n) nodes in worst case (skewed tree).

💡 For 20 nodes, this means about 20 push and pop operations, which is efficient and avoids recursion overhead.

Interview Verdict: Accepted

This approach is accepted and preferred when recursion depth is a concern or iterative solution is requested.

🧠

Morris Preorder Traversal (Threaded Binary Tree)

💡 Morris traversal is an advanced technique that achieves preorder traversal with O(1) extra space by temporarily modifying the tree structure, useful for memory-constrained environments.

Intuition

Use threaded binary tree concept: for each node, find its inorder predecessor and create a temporary link back to the current node to traverse without stack or recursion.

Algorithm

1. Initialize current node as root.
2. While current is not null, if current has no left child, visit current and move to right child.
3. Otherwise, find the rightmost node in current's left subtree (predecessor).
4. If predecessor's right is null, set it to current (thread), visit current, and move current to left child.
5. If predecessor's right is current, revert the thread to null and move current to right child.
6. Repeat until current is null.

💡 The temporary threads allow revisiting nodes without stack, but require careful creation and removal to restore tree.

</>

Code

from typing import Optional, List

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

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    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:
                predecessor.right = None
                current = current.right
    return result

# Example usage:
# root = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
# print(preorderTraversal(root))  # Output: [1, 2, 3]

Line Notes

current = rootStart traversal from the root node.

if current.left is None:If no left child, visit current and move right.

while predecessor.right and predecessor.right != current:Find rightmost node in left subtree or existing thread.

predecessor.right = currentCreate temporary thread to current node to return later.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                result.add(current.val);
                current = current.right;
            } else {
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    predecessor.right = current;
                    result.add(current.val);
                    current = current.left;
                } else {
                    predecessor.right = null;
                    current = current.right;
                }
            }
        }
        return result;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.right = new TreeNode(2);
    //     root.right.left = new TreeNode(3);
    //     Solution sol = new Solution();
    //     System.out.println(sol.preorderTraversal(root)); // Output: [1, 2, 3]
    // }
}

Line Notes

TreeNode current = root;Initialize current pointer to root for traversal.

if (current.left == null) {If no left child, visit current and move right.

while (predecessor.right != null && predecessor.right != current) {Find rightmost node in left subtree or existing thread.

predecessor.right = current;Create temporary thread to current node to revisit later.

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode* current = root;
    while (current) {
        if (!current->left) {
            res.push_back(current->val);
            current = current->right;
        } else {
            TreeNode* predecessor = current->left;
            while (predecessor->right && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (!predecessor->right) {
                predecessor->right = current;
                res.push_back(current->val);
                current = current->left;
            } else {
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
    return res;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->right = new TreeNode(2);
//     root->right->left = new TreeNode(3);
//     vector<int> result = preorderTraversal(root);
//     for (int val : result) cout << val << ' ';
//     cout << endl; // Output: 1 2 3
//     return 0;
// }

Line Notes

TreeNode* current = root;Start traversal from root node.

if (!current->left) {If no left child, visit current and move right.

while (predecessor->right && predecessor->right != current) {Find rightmost node in left subtree or existing thread.

predecessor->right = current;Create temporary thread to current node.

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function preorderTraversal(root) {
    const result = [];
    let current = root;
    while (current !== null) {
        if (current.left === null) {
            result.push(current.val);
            current = current.right;
        } else {
            let predecessor = current.left;
            while (predecessor.right !== null && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            if (predecessor.right === null) {
                predecessor.right = current;
                result.push(current.val);
                current = current.left;
            } else {
                predecessor.right = null;
                current = current.right;
            }
        }
    }
    return result;
}

// Example usage:
// const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
// console.log(preorderTraversal(root)); // Output: [1, 2, 3]

Line Notes

let current = root;Initialize current pointer to root node.

if (current.left === null) {If no left child, visit current and move right.

while (predecessor.right !== null && predecessor.right !== current) {Find rightmost node in left subtree or existing thread.

predecessor.right = current;Create temporary thread to current node to revisit later.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each edge is visited at most twice, so time is O(n). No extra stack or recursion is used, so space is O(1).

💡 For 20 nodes, this means about 40 pointer moves but no extra memory, which is optimal for memory usage.

Interview Verdict: Accepted

This approach is accepted and is the most space-efficient, but is more complex and less commonly required in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the recursive or iterative stack approach is sufficient and easiest to implement. Morris traversal is advanced and used only if space optimization is explicitly required.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursion)	O(n)	O(n) due to recursion stack	Yes (deep recursion)	N/A	Mention and code first to show understanding
2. Iterative Using Stack	O(n)	O(n) due to explicit stack	No	N/A	Code if asked for iterative or to avoid recursion
3. Morris Preorder Traversal	O(n)	O(1)	No	N/A	Mention if asked for space optimization; code only if confident

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force recursive approach, followed by iterative and advanced methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the recursive preorder traversal approach.Step 3: Implement the recursive solution and test.Step 4: Discuss iterative approach using stack and implement if time permits.Step 5: Mention Morris traversal if asked about space optimization.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of tree traversal order, recursion vs iteration, stack usage, and ability to optimize space. Clear communication and correct code are key.

Common Follow-ups

• Can you implement this iteratively? → Use a stack to simulate recursion.
• Can you optimize space usage? → Use Morris traversal to achieve O(1) space.

💡 These follow-ups test your depth of understanding and ability to optimize beyond the basic solution.

🔍

Pattern Recognition

When to Use

1) Problem involves visiting all nodes in a binary tree; 2) Output requires nodes in root-left-right order; 3) Recursive or iterative traversal is feasible; 4) Space optimization may be a follow-up.

Signature Phrases

preorder traversalvisit root node firstroot-left-right order

NOT This Pattern When

Breadth-first search (level order traversal) which uses a queue instead of stack/recursion.

Similar Problems

Binary Tree Inorder Traversal - similar but different node visiting orderBinary Tree Postorder Traversal - similar but visits children before root

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. Given the following code snippet for checking if a binary tree is symmetric, what is the final return value when called with the tree root = TreeNode(1, TreeNode(2), TreeNode(2))?

from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return t1 == t2
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

root = TreeNode(1, TreeNode(2), TreeNode(2))
print(isSymmetric(root))  # What is the output?

easy

A. false

B. Raises an exception

C. null

D. true

Solution

1. Step 1: Trace isMirror on root.left and root.right nodes with value 2

   Both nodes exist and have equal values, so recursion continues.

2. Step 2: Recursively check left.left vs right.right and left.right vs right.left (both null)

   Since both pairs are null, isMirror returns true for these calls, so overall returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Symmetric tree with equal child nodes returns true [OK]

Hint: Symmetric tree with equal children returns true [OK]

Common Mistakes:

• Confusing null checks causing exceptions
• Returning false prematurely on equal nodes
• Misreading recursion base cases

3. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?

def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result

medium

A. Missing line resetting predecessor.right = None to remove thread

B. Line moving current to current.left after creating thread

C. Line appending current.val after detecting thread

D. Line setting predecessor.right = current (creating thread)

Solution

1. Step 1: Identify thread removal step

   Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.

2. Step 2: Locate missing removal

   The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without removing thread, traversal loops endlessly [OK]

Hint: Always remove threads to restore tree [OK]

Common Mistakes:

• Forgetting to remove thread
• Appending node before removing thread
• Incorrectly creating thread

4. The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.

medium

A. Missing line to set root.left = None

B. Line: flatten(root.left)

C. Line: root.right = prev

D. Line: flatten(root.right)

Solution

1. Step 1: Review rewiring steps

   The code sets root.right = prev but does not set root.left = None, so left pointers remain.

2. Step 2: Identify missing step

   Setting root.left = None is required to ensure the flattened list has no left children.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Left pointers must be nullified to meet problem constraints [OK]

Hint: Always set root.left = None when flattening [OK]

Common Mistakes:

• Forgetting to nullify left pointers
• Misordering recursive calls causing wrong sequence
• Losing subtree references by incorrect rewiring

5. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?

def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if current_sum == targetSum:
            res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res

medium

A. Line appending left child to stack

B. Line initializing stack with root node and path

C. Line appending right child to stack

D. Line checking if current_sum == targetSum without verifying leaf node

Solution

1. Step 1: Identify condition for adding path to results

   Correct code adds path only if current node is leaf and sum matches.

2. Step 2: Locate bug

   Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing leaf check causes incorrect paths in results [OK]

Hint: Always check leaf node before adding path [OK]

Common Mistakes:

• Adding path before confirming leaf node
• Forgetting to backtrack in recursion