Lowest Common Ancestor of a Binary Search Tree – LeetCode Solution [Easy]


Given a binary search tree (BST), find the lowest common ancestor (LCA) 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 Tree that has both p and q as descendants (where we allow a node to be a descendant of itself).”

LeetCode Problem Link


root of binary search tree, node p and node q


Lowest common ancestor of nodes p and q.

  • 2 <= Number of Nodes in the Tree ≤ 100000
  • -10^9 <= Value of Nodes ≤ 10^9
  • All nodes are unique
Sample Input
Binary Search Tree
root = [6, 2, 8, 0, null, null, 10, null, 1, 9, 22]
p = 8, q = 22
Sample Output

Code Implementation

class Solution {
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) {
            return NULL;
        if (root == p || root == q) {
            return root;
        TreeNode *lNode = lowestCommonAncestor(root->left, p, q);
        TreeNode *rNode = lowestCommonAncestor(root->right, p, q);
        if (lNode && rNode) {
            return root;
        return lNode != NULL ? lNode : rNode;

Time complexity: O(n), where n is the number of nodes in tree. This is because it’s a simple tree traversal.

Leave a Reply

Your email address will not be published. Required fields are marked *