Lowest Common Ancestor of a Binary Search Tree

Problem Description

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).”

Intuition

Since tree is BST, we know every left child is strictly less than root value, and every right child is strictly greater. We determine which node is smaller and let it be smaller node, another is larger node. If root is between these two nodes, this node is the lowest common ancestor.

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		TreeNode* smaller;
		
		TreeNode* larger;

		if(p->val < q->val){
			smaller = p;
			larger = q;
		}
		else{
			smaller = q;
			larger = p;
		}

		while(root->val < (smaller->val) || root->val > (larger->val)){
			if(root->val < smaller -> val){
			root = root->right;
			}
			else if(root->val > larger->val){
			root = root->left;
			}
		}
		return root;
	}
};