Bird
Raised Fist0
Interview Preptree-dfsmediumFacebookAmazonMicrosoftGoogleBloomberg

Lowest Common Ancestor of Binary Tree

Choose your preparation mode4 modes available
📋
Problem

Imagine a family tree where you want to find the closest common ancestor of two relatives. This problem models that scenario in a binary tree structure.

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). The LCA is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). Input: root of the binary tree, and two nodes p and q. Output: the node representing their lowest common ancestor.

The number of nodes in the tree is in the range [1, 10^5].All node values are unique.p and q are different and both exist in the tree.
Edge cases: p is the root and q is a leaf → output is rootp and q are the same node → output is that nodep and q are on different subtrees → output is their common ancestor
</>
IDE
def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)function lowestCommonAncestor(root, p, q)
def lowestCommonAncestor(root, p, q):
    # Write your solution here
    pass
class Solution {
    public int lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Write your solution here
    return 0;
}
function lowestCommonAncestor(root, p, q) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: p or q node value instead of LCAReturning p or q immediately without checking if the other node is in subtree.✅ Return current node only if both left and right recursive calls are non-null or current node matches p or q.
Wrong: Root node value when p and q are in same subtreeAlways returning root or first ancestor found without checking if lower ancestor exists.✅ Use postorder DFS and return current node only if both children contain p and q.
Wrong: Null or incorrect node when p == qNot handling the case when p and q are the same node.✅ Add a check to return p immediately if p == q.
Wrong: TLE or timeout on large inputUsing repeated path searches or inefficient data structures causing O(n^2) complexity.✅ Use a single postorder DFS traversal to find LCA in O(n) time.
✓
Test Cases
t1_01basic
Input{"root":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":1}
Expected3

The LCA of nodes 5 and 1 is 3 because 3 is the lowest node that has both 5 and 1 as descendants.

t1_02basic
Input{"root":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":4}
Expected5

The LCA of nodes 5 and 4 is 5 because 5 is an ancestor of 4 and itself.

t2_01edge
Input{"root":[1],"p":1,"q":1}
Expected1

Single node tree where p and q are the same node; LCA is that node.

t2_02edge
Input{"root":[1,2],"p":1,"q":2}
Expected1

p is root and q is leaf; LCA is root node 1.

t2_03edge
Input{"root":[1,2,3],"p":2,"q":3}
Expected1

p and q are on different subtrees; LCA is root node 1.

t3_01corner
Input{"root":[3,5,1,6,2,0,8,null,null,7,4],"p":7,"q":4}
Expected2

p and q are both descendants of node 2; LCA is 2. Tests correct subtree aggregation.

t3_02corner
Input{"root":[1,2,null,3,null,4,null,5],"p":5,"q":4}
Expected4

Deep unbalanced tree tests correct ancestor detection in skewed trees.

t3_03corner
Input{"root":[1,2,3,4,5,6,7],"p":4,"q":6}
Expected1

Greedy trap test: naive approach picking first common ancestor fails; correct approach uses postorder DFS.

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

Large balanced binary tree with 100 nodes; algorithm must run in O(n) time within 2 seconds.

Practice

(1/5)
1. You need to place the minimum number of cameras in a binary tree so that every node is monitored. A camera at a node monitors its parent, itself, and its immediate children. Which approach guarantees an optimal solution for this problem?
easy
A. Brute force recursion trying all combinations of camera placements
B. Greedy postorder traversal using explicit states to track coverage and camera placement
C. Top-down dynamic programming with memoization based on node coverage
D. Level order traversal placing cameras on all nodes with uncovered children

Solution

  1. Step 1: Understand problem constraints

    The problem requires minimal cameras covering all nodes, where a camera covers parent, self, and children.
  2. Step 2: Evaluate approaches

    Brute force is exponential and inefficient. Level order placing cameras on all uncovered children is greedy but not minimal. Top-down DP is complex and less intuitive here. Greedy postorder with explicit states ensures children are processed before parent decisions, enabling minimal camera placement.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Postorder traversal with states is known optimal for this problem [OK]
Hint: Optimal solution uses postorder traversal with states [OK]
Common Mistakes:
  • Assuming level order greedy placement is minimal
  • Trying brute force without pruning
  • Confusing top-down DP with bottom-up greedy
2. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?
easy
A. Use a greedy approach by always attaching nodes as left children when possible.
B. Use dynamic programming to store subtrees and avoid recomputation.
C. Use recursion with a hash map to quickly find root indices in the inorder array.
D. Use breadth-first search to reconstruct the tree level by level.

Solution

  1. Step 1: Understand the problem constraints

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

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

    Option C -> Option C
  4. Quick Check:

    Hash map lookup avoids O(n) search per recursion [OK]
Hint: Hash map lookup avoids repeated linear searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree uniquely
  • Confusing DP with tree construction
  • Ignoring index lookup cost
3. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?
medium
A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM
B. Line returning NOT_COVERED at the end of dfs
C. Line checking if dfs(root) == NOT_COVERED after traversal
D. Line returning COVERED_NO_CAM when node is null

Solution

  1. Step 1: Identify camera placement logic

    When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.
  2. Step 2: Locate incorrect return

    The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Returning HAS_CAM is essential after placing a camera [OK]
Hint: Return HAS_CAM after placing camera to signal coverage [OK]
Common Mistakes:
  • Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
  • Forgetting to add camera if root uncovered
  • Mixing coverage states in conditions
4. What is the time complexity of the BFS-based serialization and deserialization of a binary tree with n nodes, assuming the tree is balanced? Consider both serialization and deserialization separately.
medium
A. Serialization: O(n log n), Deserialization: O(n log n)
B. Serialization: O(n), Deserialization: O(n^2)
C. Serialization: O(n), Deserialization: O(n)
D. Serialization: O(n^2), Deserialization: O(n)

Solution

  1. Step 1: Analyze serialization time

    Each node is enqueued and dequeued exactly once, so serialization is O(n).
  2. Step 2: Analyze deserialization time

    Deserialization processes each node once, reconstructing the tree in O(n) time.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Both serialization and deserialization scale linearly with number of nodes [OK]
Hint: Each node is processed once in BFS serialization/deserialization [OK]
Common Mistakes:
  • Assuming deserialization is O(n^2) due to nested loops
  • Confusing tree height with number of nodes
  • Thinking serialization is O(n log n) due to queue operations
5. What is the space complexity of the optimized recursive DFS approach for checking if a binary tree is symmetric, assuming the tree has n nodes and height h?
medium
A. O(h) due to recursion stack depth proportional to tree height
B. O(1) since no extra space besides variables is used
C. O(n) because all nodes are stored in an auxiliary data structure
D. O(n) due to storing all nodes in a queue for BFS

Solution

  1. Step 1: Identify recursion stack usage

    The recursive calls go as deep as the height of the tree, so the recursion stack uses O(h) space.
  2. Step 2: Confirm no additional data structures store all nodes

    The algorithm does not use queues or arrays to store nodes; it only uses call stack and local variables.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack space depends on tree height, not total nodes [OK]
Hint: Recursion stack space = tree height, not total nodes [OK]
Common Mistakes:
  • Confusing BFS queue space with DFS recursion stack
  • Assuming O(n) space due to node storage
  • Ignoring recursion stack space
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