LeetCode: 235. Lowest Common Ancestor of a Binary Search Tree

The Problem

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

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.

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

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) return NULL;

    if (p->val < root->val && q->val < root->val)
	    return lowestCommonAncestor(root->left, p, q);
    else if (p->val > root->val && q->val > root->val)
    	return lowestCommonAncestor(root->right, p, q);
    else return root;

}

This code helps find the common ancestor of two nodes in a tree, where the nodes are organized from the minimum to the maximum value.

• If the tree is empty (root == NULL), it stops searching and returns nothing.
• It checks if both nodes (p and q) have values less than the current node (root). If they do, it continues the search on the left side of the tree, where nodes with smaller values are located.
• If both nodes have values greater than the current node (root), it continues the search on the right side of the tree, where nodes with larger values are located.
• If one node has a smaller value and the other has a larger value than the current node, it means the current node is the common ancestor, so it returns that node.