Lowest Common Ancestor in BST Editorial

Practice Problems Link: Lowest Common Ancestor in BST

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

The lowest common ancestor of two nodes p and q is the lowest node in the binary search tree that has both p and q as its descendants. A node is also considered a descendant of itself.

Given the root node and two nodes p and q in a binary search tree, return their lowest common ancestor.

Note: You can assume that p and q will be present in the tree.

Approach

Since in a BST every node in the left subtree is less than the current node and every node in the right subtree is greater than the current node. The task is simply to find the first node from the top of the tree such that its value lies between p and q. 

Traverse the BST recursively and for each node:

• If it is greater than p and q then search for the LCA in the left subtree.
• If it is smaller than p and q then search for the LCA in the right subtree. 
• If the value of the current node lies between p and q then return the current node.

Analysis

• Time Complexity: O(Height of BST)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
    if (p->data > root->data && q->data > root->data) {
		return lowestCommonAncestor(root->right, p, q);
	}
	if (p->data < root->data && q->data < root->data) {
		return lowestCommonAncestor(root->left, p, q);
	}
	return root;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	
	Node lowestCommonAncestor(Node root, Node p, Node q) {
	    if (p.data > root.data && q.data > root.data) {
			return lowestCommonAncestor(root.right, p, q);
		}
		if (p.data < root.data && q.data < root.data) {
			return lowestCommonAncestor(root.left, p, q);
		}
		return root;
	}
}