A Simple Example of a Recursive Algorithm on a Binary Search Tree
A C++ recursive approach to solve Leetcode 235. Lowest Common Ancestor of a Binary Search Tree.
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, 10^5]
. -10^9 <= Node.val <= 10^9
.- All
Node.val
are unique. p != q
.p
andq
will exist in the BST.
Solution: Recursion
Note that in a BST, the values of a node
and its children left
and right
satisfy
left.value < node.value < right.value.
It lets you know which branch (left or right) of the root
the nodes p
and q
belong to.
Code
#include <iostream>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr)
{
}
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (p->val < root->val && q->val < root->val)
{
return lowestCommonAncestor(root->left, p, q);
}
else if (root->val < p->val && root->val < q->val)
{
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
int main()
{
TreeNode zero(0);
TreeNode three(3);
TreeNode five(5);
TreeNode four(4);
four.left = &three;
four.right = &five;
TreeNode two(2);
two.left = &zero;
two.right = &four;
TreeNode seven(7);
TreeNode nine(9);
TreeNode eight(8);
eight.left = &seven;
eight.right = &nine;
TreeNode six(6);
six.left = &two;
six.right = &eight;
cout << lowestCommonAncestor(&six, &two, &eight)->val << endl;
cout << lowestCommonAncestor(&six, &two, &four)->val << endl;
cout << lowestCommonAncestor(&two, &two, &zero)->val << endl;
}
Output:
6
2
2
Code explanation
- The function takes three arguments:
root
,p
, andq
.root
represents the root node of the BST, whilep
andq
represent the two nodes for which we want to find the lowest common ancestor. - The code starts with a recursive approach and a divide-and-conquer strategy. It checks whether the values of
p
andq
are less than the value of the currentroot
node or greater than the value of the currentroot
node. These comparisons are made using the values stored inp->val
,q->val
, androot->val
. - If both
p
andq
are less thanroot->val
, which means that both nodesp
andq
are in the left subtree of the currentroot
. In this case, the code recursively callslowestCommonAncestor(root->left, p, q)
to search for the LCA in the left subtree. - If both
p
andq
are greater thanroot->val
, which means that both nodesp
andq
are in the right subtree of the currentroot
. In this case, the code recursively callslowestCommonAncestor(root->right, p, q)
to search for the LCA in the right subtree. - If neither of the above conditions is met, it means that one node is in the left subtree, and the other is in the right subtree, or one of them is the current
root
node itself. In either case, the currentroot
node is the lowest common ancestor and the code returnsroot
. - The recursion continues until it finds the LCA or reaches a null node (indicating that one of the nodes
p
orq
was not found in the subtree). In the latter case, the code returnsroot
, which might be a valid LCA if one of the nodes is present in the subtree ornullptr
if both nodes are not in the tree.
Complexity
This solution leverages the properties of a BST, where the left subtree contains nodes with values less than the root, and the right subtree contains nodes with values greater than the root, to efficiently find the lowest common ancestor of two nodes p
and q
.
- Runtime:
O(h)
, whereh
is the height of the tree. In a balanced BST, this height is typicallylog(N)
forN
nodes. - Extra space:
O(1)
.
This article was originally published at https://www.leetsolve.com, where you can learn basic data structures and algorithms through solving coding challenges.
What do you think about this article? Please leave a comment below. Thank you very much!
Get my book 10 Classic Coding Challenges for FREE.