#235

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Lowest Common Ancestor of a Binary Search Tree

Find the lowest common ancestor (LCA) of two nodes in a binary search tree, using binary-tree traversal and state tracking.

tree depth first search binary search tree binary tree

Problem Statement

Given a binary search tree (BST) and two nodes, p and q, you need 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 nodes as descendants. It is guaranteed that both nodes p and q will exist in the BST and that p is not equal to q.

To solve this problem, traverse the BST from the root. At each node, check the relative positions of p and q. If both p and q are in the left or right subtree of the current node, move in the respective direction. If p and q are in different subtrees, the current node is the LCA.

Examples

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

The LCA of nodes 2 and 8 is 6.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

Output: 2

The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3

Input: root = [2,1], p = 2, q = 1

Output: 2

Example details omitted.

Constraints

The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the BST.

Solution Approach

Binary Search Tree Property

Since the tree is a binary search tree, it has a property where for any node, values in the left subtree are smaller, and values in the right subtree are larger. This property helps in efficiently determining the direction of traversal (left or right) while searching for the LCA.

Depth-First Search (DFS)

Using a DFS traversal, we explore the tree starting from the root. At each node, check if both p and q lie in the left or right subtrees. If so, move to the respective subtree. If p and q lie in different subtrees, the current node is the LCA.

State Tracking for Efficient Search

Track the state of traversal to avoid unnecessary rechecking of nodes. By comparing the values of the current node with p and q, we can decide whether to move left or right or return the current node as the LCA.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the depth of the tree, which can be O(log n) for a balanced tree and O(n) for a skewed tree. The space complexity is O(1) for the iterative approach or O(h) for the recursive DFS approach, where h is the height of the tree.

What Interviewers Usually Probe

Candidate correctly identifies the LCA concept and binary search tree traversal patterns.
Candidate efficiently explains the use of DFS and state tracking in LCA search.
Candidate discusses time and space complexities relevant to the tree's structure and traversal.

Common Pitfalls or Variants

Common pitfalls

Confusing binary tree traversal with BFS, leading to inefficient solutions.
Incorrectly identifying the LCA when both nodes are in the same subtree.
Not considering the edge case where one of the nodes is the root.

Follow-up variants

Find the LCA for multiple pairs of nodes in a single BST.
Find the LCA in a binary tree (not necessarily a BST).
Find the LCA in a tree with non-unique node values.

FAQ

How do I approach the Lowest Common Ancestor problem in a Binary Search Tree?

Start by utilizing the BST property to narrow down the search direction. Use DFS to explore the tree and track the state of traversal to identify the LCA.

What is the key traversal method for solving the Lowest Common Ancestor problem?

The primary traversal method is Depth-First Search (DFS), where you explore each subtree and determine if both nodes are present in the same subtree.

What should I consider when analyzing the time complexity for this problem?

The time complexity depends on the tree's height, which is O(log n) for a balanced tree and O(n) for a skewed tree. Space complexity is O(h) for a recursive approach.

What is the significance of the binary search tree property in this problem?

The binary search tree property allows for efficient traversal and narrowing down the search for the LCA by checking whether the nodes lie in the left or right subtree of the current node.

How can GhostInterview help me with the Lowest Common Ancestor problem?

GhostInterview provides a structured approach, highlighting the critical traversal patterns and common pitfalls to avoid, ensuring an efficient and clear solution.

terminal

Solution

Solution 1: Iteration

Starting from the root node, we traverse the tree. If the current node's value is less than both $\textit{p}$ and $\textit{q}$ values, it means that $\textit{p}$ and $\textit{q}$ should be in the right subtree of the current node, so we move to the right child. If the current node's value is greater than both $\textit{p}$ and $\textit{q}$ values, it means that $\textit{p}$ and $\textit{q}$ should be in the left subtree, so we move to the left child. Otherwise, it means the current node is the lowest common ancestor of $\textit{p}$ and $\textit{q}$, so we return the current node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(
        self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
    ) -> 'TreeNode':
        while 1:
            if root.val < min(p.val, q.val):
                root = root.right
            elif root.val > max(p.val, q.val):
                root = root.left
            else:
                return root

Solution 2: Recursion

We can also use a recursive approach to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(
        self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
    ) -> 'TreeNode':
        while 1:
            if root.val < min(p.val, q.val):
                root = root.right
            elif root.val > max(p.val, q.val):
                root = root.left
            else:
                return root

Continue Practicing

#230 kth smallest element in a bst #99 recover binary search tree #98 validate binary search tree