Find lowest common ancestor in tree
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the root of a binary search tree (BST) and two distinct nodes p and q that are guaranteed to exist in the tree.
Task (BST case):
- Find the lowest common ancestor (LCA) of nodes p and q.
- The LCA is defined as the lowest (deepest) node in the tree that has both p and q as descendants (a node can be a descendant of itself).
Assumptions:
- The tree satisfies the BST property: for any node x, all nodes in the left subtree have values < x.val, and all nodes in the right subtree have values > x.val.
- You may receive p and q as node references or as values; clarify with the interviewer, and handle one consistent version.
Follow-up:
- How would your approach change if the tree is a general binary tree **without** the BST property?
- In the general binary tree case:
- The tree may not be balanced.
- Node values are not ordered.
- p and q are still guaranteed to exist.
Describe algorithms for both the BST and the general binary tree cases and analyze their time and space complexity.
Quick Answer: This question evaluates understanding of tree data structures and the lowest common ancestor concept, contrasting use of binary search tree ordering with the general binary tree case while requiring algorithmic time and space complexity reasoning in the Coding & Algorithms domain.