Katkat
Back

Find the Lowest Common Ancestor in a Binary Tree

MicrosoftMachine Learning Engineer · HR Screen
MediumMachine Learning EngineerHR ScreenCoding & Algorithms

Last updated

This problem tests tree traversal techniques and recursion logic to identify the deepest node that is an ancestor to two specified nodes in an arbitrary binary tree.

Problem Statement

Given the root of a binary tree and two distinct integer values p and q, write a function to find the Lowest Common Ancestor (LCA) of the two nodes. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Function Signature

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

def find_lca(root: TreeNode, p: int, q: int) -> TreeNode:
    # Implementation here

Constraints

  • The tree is not necessarily a Binary Search Tree.
  • All vals are unique.
  • The number of nodes in the tree is in the range [2, 10^5].
  • p and q are guaranteed to exist in the tree.

Example 1

Input: root = [3, 5, 1, 6, 2, 0, 8], p = 5, q = 1 Output: Node with value 3 Explanation: The node 5 and node 1 are both children of node 3.

Example 2

Input: root = [3, 5, 1, 6, 2, 0, 8], p = 5, q = 4 (Note: 4 is a child of 2) Output: Node with value 5 Explanation: Node 5 is an ancestor of node 4, so 5 is the LCA.

Edge Cases

  • One node is the parent of the other.
  • The LCA is the root node.
  • The tree is a skewed linked list structure.

Hints

Hint 1

Consider a recursive approach where each function call returns the node itself if it matches p or q, or indicates if one of the targets was found in its subtrees.

Hint 2

If both the left and right recursive calls return a non-null node, it means the current node is the branching point where p and q meet.

Hint 3

If only one recursive call returns a node, bubble that node up as it represents the found target or the LCA found deeper in that subtree.

Follow-up questions

  • How would your approach change if each node had a pointer to its parent?
  • What is the time and space complexity of your solution in the worst case (a skewed tree)?
  • How would you modify your algorithm if you needed to find the LCA for a list of k nodes instead of just two?