Lowest Common Ancestor of a Binary Search Tree Leetcode Solution

Problem Statement:

Lowest Common Ancestor of a Binary Search Tree Leetcode Solution – Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Note: “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:

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.

Approach:

Idea:

Iterate in BST

1. Calculate the maximum between the value of node p and node q and store the value in maxi, and in the same way, calculate the minimum between the value of node p and node q and store the value in mini.
2. We keep iterating root in BST and check :
   1. If  the value of root node > maxi then both node p and q belong to the left subtree, go to the left of the tree.
   2. If  the value of root node< mini then both node p and q belong to the right subtree, go to the right of the tree.
   3. Now, mini <= the value of root node <= maxi the current root is the LCA between q and p.

Code:

C++ Program of  Lowest Common Ancestor of a Binary Search Tree:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int mini = min(p->val, q->val);
        int maxi = max(p->val, q->val);
        while (root != nullptr) {
            if (root->val > maxi)
                root = root->left;
            else if (root->val < mini)
                root = root->right;
            else 
                return root;
        }
        return nullptr;
        
    }
};

Java Program of  Lowest Common Ancestor of a Binary Search Tree:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int mini = Math.min(p.val, q.val);
        int maxi = Math.max(p.val, q.val);
        while (root != null) {
            if (root.val > maxi)
                root = root.left;
            else if (root.val < mini)
                root = root.right;
            else 
                return root;
        }
        return null;
    }
}

Complexity Analysis for Lowest Common Ancestor of a Binary Search Tree Leetcode Solution:

Time Complexity:

The Time Complexity of the code is O(H), where H is the height of the Binary Tree.

Space Complexity:

The Space Complexity of the code is O(1) because we don’t need any extra space to solve this problem.