Katkat
Back

Find the Lowest Common Ancestor in a Binary Tree

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests tree traversal techniques and recursive logic to identify the deepest node that is an ancestor to two specified nodes within a binary tree.

Problem Statement

Given the root of a binary tree, find the Lowest Common Ancestor (LCA) of two given nodes, p and q. The LCA is defined between two nodes p and q 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).

Function Signature

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

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9.
  • All Node.val are unique.
  • p and q are guaranteed to exist in the tree.

Examples

Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: Since node 5 is a parent of 4, the LCA is 5.

Edge Cases

  • The tree contains only two nodes.
  • One node is the direct parent of the other.
  • The tree is a degenerate (linked list) tree structure.

Hints

Hint 1

Consider a recursive approach: what happens if the current node is null, or if it matches p or q?

Hint 2

If the current node is null or matches p or q, return the current node; otherwise, look for p and q in the left and right subtrees.

Hint 3

If both subtrees return a non-null node, then the current node is the LCA; if only one subtree returns a node, that node is the LCA.

Follow-up questions

  • How would you optimize this if you were given parent pointers for each node instead of the root?
  • What is the space complexity of your solution, and can you improve it if the tree is skewed?
  • If this were a Binary Search Tree instead of a standard Binary Tree, how would your algorithm change to improve efficiency?