235. Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree (LeetCode 235) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Lowest Common Ancestor (LCA) Finding subpattern.

• Blind 75 · #29 of 75 · Trees
• NeetCode 150 · #52 of 150 · Trees
• NeetCode 250 · #97 of 250 · Trees

How to solve Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree is a Lowest Common Ancestor problem, part of Tree Traversal Patterns (DFS & BFS). Find lowest common ancestor in binary trees and BSTs using recursive and iterative approaches.

Work towards the solution in these steps:

1. Recall that a Binary Search Tree (BST) has the property where the left child is smaller and the right child is larger than the parent node.
2. Since the tree is a BST, consider how the values of the two nodes p and q relate to the current node's value to guide your traversal direction.
3. Think about traversing the tree starting from the root and deciding whether to go left, right, or stop based on the values of p, q, and the current node.

The reference solution runs in O(h) time and O(n) space.

The Lowest Common Ancestor of a Binary Search Tree solution and editorial walks through the full approach with reference code.

Problem statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: 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 Explanation: 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

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.

Topics and companies

Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree.

Reported in interviews at Amazon, Facebook, LinkedIn, Oracle, Microsoft.

How to practise Lowest Common Ancestor of a Binary Search Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(h) time and O(n) space.

Open Lowest Common Ancestor of a Binary Search Tree in the code editor, or read the Lowest Common Ancestor of a Binary Search Tree editorial for a worked solution with its approach and complexity analysis.

Where Lowest Common Ancestor of a Binary Search Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Lowest Common Ancestor (LCA) Finding subpattern
• The full DSA patterns sheet

Problems related to Lowest Common Ancestor of a Binary Search Tree

Other problems that use the same Lowest Common Ancestor (LCA) Finding and Tree Traversal Patterns (DFS & BFS) techniques:

• Lowest Common Ancestor of a Binary Tree — Medium, same subpattern
• All Nodes Distance K in Binary Tree — Medium, same pattern
• Balanced Binary Tree — Easy, same pattern
• Binary Search Tree Iterator — Medium, same pattern
• Binary Tree Inorder Traversal — Easy, same pattern
• Binary Tree Level Order Traversal — Medium, same pattern

Lowest Common Ancestor of a Binary Search Tree FAQ