Lowest Common Ancestor of a Binary Search Tree Leetcode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Facebook Google LinkedIn Microsoft Oracle Twitter Uber
Binary Search Tree Huawei Reddit Tree WalmartViews 2753

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:

Lowest Common Ancestor of a Binary Search Tree Leetcode Solution

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:

Lowest Common Ancestor of a Binary Search Tree Leetcode Solution

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.

case1

case2   case3

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.

Translate »