House Robber III (On Tree)

🎯

House Robber III (On Tree)

mediumDPAmazonGoogle

Imagine a thief planning to rob houses arranged in a neighborhood shaped like a tree. The thief cannot rob two directly connected houses to avoid alerting the police.

💡 This problem is a classic example of dynamic programming on trees, which can be tricky because unlike arrays, trees have hierarchical structures without linear order. Beginners often struggle to understand how to carry state information up and down the tree and how to avoid recomputation.

📋

Problem Statement

Given a binary tree where each node represents the amount of money stashed in a house, determine the maximum amount of money the thief can rob without robbing two directly connected houses (parent and child). Return the maximum amount of money that can be robbed.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^4

💡

Example

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

Output7

Rob houses with values 3 (root), 3 (right child of left child), and 1 (right child of right child). Total = 3 + 3 + 1 = 7.

Input"root = [3,4,5,1,3,null,1]"

Output9

Rob houses with values 4 and 5. Total = 4 + 5 = 9.

• Single node tree → output is node's value
• All nodes have zero value → output is 0
• Linear tree (like a linked list) → behaves like House Robber I
• Complete binary tree with equal values → choose alternate levels

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the current node with the highest value fails because it might force skipping large sums in children or grandchildren. For example, picking a parent with value 10 might prevent robbing two children with values 6 and 7, losing a total of 13.

DP state:

dp[node] = (max_if_not_robbed, max_if_robbed) where max_if_not_robbed is the max money if we do NOT rob this node, and max_if_robbed is the max money if we rob this node.

Recurrence:dp[node].rob = node.val + sum of dp[child].not_rob for all children; dp[node].not_rob = sum of max(dp[child].rob, dp[child].not_rob) for all children

If we rob the current node, we cannot rob its children, so we add node's value plus the max money from not robbing children. If we don't rob the current node, we take the max of robbing or not robbing each child.

⚠️

Common Mistakes

Forgetting to skip children when robbing current node

Incorrectly sums values leading to overcounting and wrong answer

✅ Ensure when robbing current node, add only grandchildren's values, not children

Not caching results in recursion

Exponential time leading to TLE

✅ Use memoization or bottom-up DP to store intermediate results

Mixing up the order of post-order traversal

Computes parent before children, leading to missing data and errors

✅ Always compute children before parent in DP on trees

Using node values as keys in memo without node identity

Incorrect caching leading to wrong results if values repeat

✅ Use node references or unique IDs as keys in memo

🧠

Brute Force (Pure Recursion)

💡 This approach explores all possibilities by deciding for each node whether to rob it or not, without caching results. It is important to understand this to grasp the problem's complexity and why optimization is needed.

Intuition

At each node, we try robbing it and skipping its children, or skipping it and robbing its children, then take the maximum.

Algorithm

1. Start at the root node.
2. For each node, recursively compute the max money if we rob it (skip children) and if we don't rob it (consider children).
3. Return the maximum of robbing or not robbing the root.
4. Combine results from subtrees to get the final answer.

💡 The recursion tree grows exponentially because each node branches into two choices, making it hard to track without memoization.

Recurrence:f(node) = max(node.val + sum of f(grandchildren), sum of f(children))

</>

Code

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

def rob(root):
    if not root:
        return 0
    val = root.val
    if root.left:
        val += rob(root.left.left) + rob(root.left.right)
    if root.right:
        val += rob(root.right.left) + rob(root.right.right)
    return max(val, rob(root.left) + rob(root.right))

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7

Line Notes

if not root:Base case: no house means no money

val = root.valStart with robbing current node's value

if root.left:Add grandchildren's values if left child exists

return max(val, rob(root.left) + rob(root.right))Choose max between robbing current node plus grandchildren or robbing children

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

public class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(val, rob(root.left) + rob(root.right));
    }

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

Line Notes

if (root == null) return 0;Base case: no node means no money

int val = root.val;Start with current node's value

if (root.left != null)Check if left child exists to add grandchildren

return Math.max(val, rob(root.left) + rob(root.right));Choose max between robbing current node plus grandchildren or robbing children

#include <iostream>
using namespace std;

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

class Solution {
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        int val = root->val;
        if (root->left) {
            val += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            val += rob(root->right->left) + rob(root->right->right);
        }
        return max(val, rob(root->left) + rob(root->right));
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}

Line Notes

if (!root) return 0;Base case: no node means no money

int val = root->val;Start with current node's value

if (root->left)Check if left child exists to add grandchildren

return max(val, rob(root->left) + rob(root->right));Choose max between robbing current node plus grandchildren or robbing children

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

function rob(root) {
    if (!root) return 0;
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    return Math.max(val, rob(root.left) + rob(root.right));
}

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

Line Notes

if (!root) return 0;Base case: no house means no money

let val = root.val;Start with robbing current node's value

if (root.left)Add grandchildren's values if left child exists

return Math.max(val, rob(root.left) + rob(root.right));Choose max between robbing current node plus grandchildren or robbing children

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each node branches into two recursive calls for grandchildren and children, leading to exponential calls.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's structure.

🧠

Top-Down Memoization

💡 Memoization caches results of subproblems to avoid recomputation, drastically improving efficiency while keeping the recursive structure.

Intuition

Store the maximum money for each node once computed, so repeated calls return cached results.

Algorithm

1. Use a hash map to store results for each node.
2. For each node, check if result is cached; if yes, return it.
3. Otherwise, compute max money by robbing or skipping the node recursively.
4. Cache and return the computed result.

💡 Memoization turns exponential recursion into linear by remembering answers.

Recurrence:f(node) = max(node.val + sum of f(grandchildren), sum of f(children)) with memoization

</>

Code

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

def rob(root):
    memo = {}
    def dfs(node):
        if not node:
            return 0
        if node in memo:
            return memo[node]
        val = node.val
        if node.left:
            val += dfs(node.left.left) + dfs(node.left.right)
        if node.right:
            val += dfs(node.right.left) + dfs(node.right.right)
        res = max(val, dfs(node.left) + dfs(node.right))
        memo[node] = res
        return res
    return dfs(root)

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7

Line Notes

memo = {}Initialize cache to store results for nodes

if node in memo:Return cached result if available

val = node.valStart with robbing current node's value

memo[node] = resCache computed result to avoid recomputation

import java.util.HashMap;

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

public class Solution {
    private HashMap<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }
        int res = Math.max(val, rob(root.left) + rob(root.right));
        memo.put(root, res);
        return res;
    }

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

Line Notes

private HashMap<TreeNode, Integer> memo = new HashMap<>();Cache to store results for nodes

if (memo.containsKey(root)) return memo.get(root);Return cached result if available

int val = root.val;Start with current node's value

memo.put(root, res);Cache computed result to avoid recomputation

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

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

struct TreeNodeHash {
    size_t operator()(const TreeNode* node) const {
        return hash<long long>()((long long)node);
    }
};

class Solution {
    unordered_map<TreeNode*, int, TreeNodeHash> memo;
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        if (memo.count(root)) return memo[root];
        int val = root->val;
        if (root->left) {
            val += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            val += rob(root->right->left) + rob(root->right->right);
        }
        int res = max(val, rob(root->left) + rob(root->right));
        memo[root] = res;
        return res;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}

Line Notes

unordered_map<TreeNode*, int, TreeNodeHash> memo;Cache to store results for nodes

if (memo.count(root)) return memo[root];Return cached result if available

int val = root->val;Start with current node's value

memo[root] = res;Cache computed result to avoid recomputation

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

const memo = new Map();
function rob(root) {
    if (!root) return 0;
    if (memo.has(root)) return memo.get(root);
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    const res = Math.max(val, rob(root.left) + rob(root.right));
    memo.set(root, res);
    return res;
}

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

Line Notes

const memo = new Map();Cache to store results for nodes

if (memo.has(root)) return memo.get(root);Return cached result if available

let val = root.val;Start with current node's value

memo.set(root, res);Cache computed result to avoid recomputation

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack and memo

Each node is computed once and cached, so linear time.

💡 For n=10^5, this is efficient enough to run within seconds.

Interview Verdict: Accepted

Memoization makes the solution efficient and practical for large inputs.

🧠

Bottom-Up DP with Post-Order Traversal

💡 This approach uses a bottom-up traversal to compute the answer for each node based on its children, avoiding recursion overhead and making the logic clearer.

Intuition

For each node, compute two values: max money if robbed and max money if not robbed, using children's results.

Algorithm

1. Traverse the tree in post-order (children before parent).
2. For each node, compute two values: rob and not_rob.
3. rob = node.val + sum of not_rob from children.
4. not_rob = sum of max(rob, not_rob) from children.
5. Return max of rob and not_rob at root.

💡 This approach cleanly separates the two states per node and uses children's results to build parent's answer.

Recurrence:dp[node].rob = node.val + sum(dp[child].not_rob); dp[node].not_rob = sum(max(dp[child].rob, dp[child].not_rob))

</>

Code

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

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7

Line Notes

def dfs(node):Helper function to return tuple (not_rob, rob) for node

if not node:Base case returns zero for both states

rob_node = node.val + left[0] + right[0]Rob current node plus not robbing children

not_rob_node = max(left) + max(right)Don't rob current node, take max of rob or not rob children

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

public class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int rob = node.val + left[0] + right[0];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{notRob, rob};
    }

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

Line Notes

private int[] dfs(TreeNode node)Returns array with two states: notRob and rob

if (node == null) return new int[]{0, 0};Base case returns zero for both states

int rob = node.val + left[0] + right[0];Rob current node plus not robbing children

int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);Don't rob current node, take max of rob or not rob children

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

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

class Solution {
public:
    pair<int,int> dfs(TreeNode* node) {
        if (!node) return {0,0};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        int rob = node->val + left.first + right.first;
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        return {notRob, rob};
    }

    int rob(TreeNode* root) {
        auto res = dfs(root);
        return max(res.first, res.second);
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}

Line Notes

pair<int,int> dfs(TreeNode* node)Returns pair (notRob, rob) for node

if (!node) return {0,0};Base case returns zero for both states

int rob = node->val + left.first + right.first;Rob current node plus not robbing children

int notRob = max(left.first, left.second) + max(right.first, right.second);Don't rob current node, take max of rob or not rob children

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

function rob(root) {
    function dfs(node) {
        if (!node) return [0, 0];
        const left = dfs(node.left);
        const right = dfs(node.right);
        const rob = node.val + left[0] + right[0];
        const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [notRob, rob];
    }
    const res = dfs(root);
    return Math.max(res[0], res[1]);
}

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

Line Notes

function dfs(node)Returns array [notRob, rob] for node

if (!node) return [0, 0];Base case returns zero for both states

const rob = node.val + left[0] + right[0];Rob current node plus not robbing children

const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);Don't rob current node, take max of rob or not rob children

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Each node is visited once in post-order traversal.

💡 For n=10^5, this approach is efficient and scalable.

Interview Verdict: Accepted

This is the optimal and cleanest approach for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with post-order traversal is the best approach to implement in interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(n)	O(n) recursion stack + memo	Yes (deep recursion)	Yes	Good to mention and code if comfortable
3. Bottom-Up DP (Post-Order)	O(n)	O(n) recursion stack	Yes (deep recursion)	Yes	Best approach to code in interview

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up DP with post-order traversal as the optimal solution.Step 5: Code the bottom-up DP solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of tree DP, ability to optimize recursion with memoization, and clarity in explaining state definitions and transitions.

Common Follow-ups

• What if the tree is a linked list? → The problem reduces to House Robber I.
• Can you reconstruct which nodes were robbed? → Yes, by tracking choices during DP.

💡 These follow-ups test your ability to adapt solutions and extend them to practical scenarios.

🔍

Pattern Recognition

When to Use

1) Problem involves trees, 2) Need to optimize choices with constraints on adjacency, 3) Maximize sum or value, 4) Overlapping subproblems exist.

Signature Phrases

cannot rob two directly connected housesmaximum amount of moneybinary tree structure

NOT This Pattern When

Problems involving arbitrary graphs or no adjacency constraints are different and require other techniques.

Similar Problems

House Robber I - linear array version of the problemHouse Robber II - circular array versionBinary Tree Maximum Path Sum - similar tree DP but different constraints

Practice

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. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?

easy

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Calculate tree height

   Height h = 3 (nodes 1 -> 2 -> 4).

2. Step 2: Binary search on last level nodes

   Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]

Hint: Count = perfect nodes + last level nodes found [OK]

Common Mistakes:

• Off-by-one in binary search bounds
• Miscounting last level nodes

3. You are given a binary tree and need to find the longest path from the root node down to the farthest leaf node. Which algorithmic approach guarantees an optimal solution to determine this maximum depth?

easy

A. Dynamic Programming with memoization on node values

B. Greedy traversal picking the first child node at each step

C. Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all nodes

D. Sorting nodes by value and selecting the deepest node

Solution

1. Step 1: Understand the problem requires exploring all paths from root to leaves

   Finding maximum depth means checking every path from root to leaves, so partial or greedy approaches won't guarantee correctness.

2. Step 2: Identify algorithms that explore all nodes

   DFS or BFS traverse all nodes systematically, ensuring the maximum depth is found. Greedy or sorting approaches do not consider all paths.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DFS and BFS both visit all nodes to find max depth [OK]

Hint: Max depth requires full traversal, not greedy or sorting [OK]

Common Mistakes:

• Assuming greedy traversal finds max depth
• Confusing max depth with max node value
• Thinking sorting nodes helps depth calculation

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

5. What is the time complexity of the parent pointer + ancestor set approach for finding the Lowest Common Ancestor in a binary tree with n nodes and height h?

medium

A. O(h^2) because ancestor set lookups take O(h) each and we do up to h lookups

B. O(n^2) because each node's parent is checked multiple times

C. O(n) to build parent map plus O(h) to find LCA, total O(n)

D. O(n log n) due to sorting ancestors before comparison

Solution

1. Step 1: Identify parent map construction cost

   Building the parent map requires visiting each node once, O(n).

2. Step 2: Analyze ancestor set and LCA search

   Ancestor set insertion and lookup are O(1) average. Traversing up to height h for p and q is O(h). Total is O(n) + O(h) ≈ O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Parent map O(n) + ancestor lookup O(h) = O(n) total [OK]

Hint: Parent map build dominates; ancestor lookup is O(h) [OK]

Common Mistakes:

• Confusing ancestor set lookup as O(h)
• Assuming sorting ancestors needed
• Overestimating repeated parent checks