Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoft

Binary Tree Preorder Traversal

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Recursion)O(n)O(n) due to recursion stackYes (deep recursion)N/AMention and code first to show understanding
2. Iterative Using StackO(n)O(n) due to explicit stackNoN/ACode if asked for iterative or to avoid recursion
3. Morris Preorder TraversalO(n)O(1)NoN/AMention 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/5)
1. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)
easy
A. True
B. False
C. Raises an exception due to null pointer
D. Returns True only if the root value equals targetSum

Solution

  1. Step 1: Trace the path sums

    Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.
  2. Step 2: Confirm code logic

    The DFS returns True as soon as it finds the matching path sum at a leaf node.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Path 5↔4↔11↔2 sums to 22, so return True [OK]
Hint: Check all root-to-leaf paths, not just partial sums [OK]
Common Mistakes:
  • Stopping at non-leaf nodes
  • Ignoring leaf node condition
2. What is the time complexity of the iterative DFS solution for finding all root-to-leaf paths with a given sum in a binary tree with N nodes and maximum path length L?
medium
A. O(N) because each node is visited once
B. O(N^2) because all pairs of nodes are compared during traversal
C. O(N * L) because each node's path is copied when pushed onto the stack
D. O(L) because only the path length affects complexity

Solution

  1. Step 1: Identify operations per node

    Each node is visited once, but path copying of length up to L occurs when pushing onto stack.
  2. Step 2: Calculate total complexity

    Copying paths of length L for up to N nodes leads to O(N * L) time complexity.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Path copying dominates, so complexity is O(N * L) [OK]
Hint: Path copying causes O(N * L), not just O(N) [OK]
Common Mistakes:
  • Assuming O(N) ignoring path copying
  • Confusing with quadratic complexity from unrelated operations
3. Consider the following buggy code for checking if a binary tree is symmetric. Which line contains the subtle bug that causes incorrect results for asymmetric trees?
def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return True
        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
medium
A. Line 5: if t1.val != t2.val: return False
B. Line 3: if not t1 or not t2: return True
C. Line 6: return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
D. Line 8: return isMirror(root.left, root.right) if root else True

Solution

  1. Step 1: Analyze base case for null nodes

    The line returns true if either t1 or t2 is null, but it should only return true if both are null.
  2. Step 2: Identify that returning true when only one node is null causes false positives

    This causes asymmetric trees with missing nodes on one side to be incorrectly considered symmetric.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Base case must check both nodes null equality, not just one [OK]
Hint: Base case must return true only if both nodes are null [OK]
Common Mistakes:
  • Returning true if only one node is null
  • Forgetting to check node values before recursion
  • Mixing left and right subtree comparisons
4. If the binary tree nodes can have parent pointers in addition to left and right children, which modification to the iterative one-stack postorder traversal algorithm can eliminate the need for the last_visited variable?
hard
A. Use the parent pointer to move back up after visiting a node's children, tracking traversal direction
B. Push nodes twice onto the stack to simulate postorder without tracking last visited
C. Perform a preorder traversal and reverse the output list at the end
D. Use two stacks: one for traversal and one for output, ignoring parent pointers

Solution

  1. Step 1: Understand role of last_visited

    Last_visited tracks if right child was processed to avoid revisiting; parent pointers can provide traversal direction.
  2. Step 2: Use parent pointer to detect traversal direction

    By moving up via parent pointer, algorithm knows if coming from left or right child, eliminating need for last_visited.
  3. Step 3: Compare other options

    Options B and D ignore parent pointers; A reverses preorder but does not leverage parent pointers; C uses parent pointers effectively.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Parent pointers enable direction-aware traversal without extra state [OK]
Hint: Parent pointers track traversal direction, removing last_visited [OK]
Common Mistakes:
  • Ignoring parent pointers
  • Using two stacks unnecessarily
  • Reversing preorder output without parent info
5. Suppose the binary tree nodes have parent pointers already, but the tree is very deep (height h). You want to find the Lowest Common Ancestor of two nodes p and q. Which approach is best to optimize time and space, and why?
hard
A. Use brute force by checking all ancestors of p and q repeatedly until common ancestor is found.
B. Use the parent pointer + ancestor set approach, building a set for p's ancestors and then traversing q's ancestors.
C. Use recursive DFS from root to find paths to p and q, then compare paths to find LCA.
D. Use the parent pointer + two-pointer technique: move the deeper node up until both nodes are at the same depth, then move both up simultaneously until they meet.

Solution

  1. Step 1: Understand problem constraints

    Nodes have parent pointers, tree is deep, so space usage matters.
  2. Step 2: Evaluate approaches

    Ancestor set approach (B) uses O(h) space. Recursive DFS (C) and brute force (D) are inefficient for deep trees.
  3. Step 3: Two-pointer technique

    Moving deeper node up to equalize depth, then moving both up simultaneously uses O(1) space and O(h) time, optimal for deep trees.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Two-pointer approach optimizes space and time for deep trees with parent pointers [OK]
Hint: Two-pointer approach uses O(1) space for LCA with parent pointers [OK]
Common Mistakes:
  • Using ancestor sets unnecessarily
  • Recursing from root wasting time
  • Brute force repeated ancestor checks
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