Skip to content

Day 14 - Lowest Common Ancestor in a BST.md

Latest commit

 

History

History
251 lines (175 loc) · 6.94 KB

Day 14 - Lowest Common Ancestor in a BST.md

File metadata and controls

251 lines (175 loc) · 6.94 KB
Raw
Difficulty Easy
Source 160 Days of Problem Solving
Tags
Tree
Binary Search Tree

🚀 Day 14. Lowest Common Ancestor in a BST 🧠

The problem can be found at the following link: Question Link

💡 Problem Description:

Given a Binary Search Tree (BST) with unique values and two nodes n1 and n2 (where n1 != n2), find the Lowest Common Ancestor (LCA) of the two given nodes in the BST.

The LCA is the lowest node in the BST that has both n1 and n2 as descendants (a node is also considered its own descendant).

🔍 Example Walkthrough:

Example 1:

Input:

        5  
       / \  
      4   6  
     /     \  
    3       7  
             \  
              8

n1 = 7, n2 = 8

Output:

7

Explanation:

The lowest common ancestor of 7 and 8 is 7 itself.

Example 2:

Input:

         20  
        /  \  
       8    22  
      / \      
     4   12    
        /  \  
       10  14

n1 = 8, n2 = 14

Output:

8

Explanation:

8 is the lowest node that is an ancestor of both 8 and 14.

Example 3:

Input:

    2  
   / \  
  1   3

n1 = 1, n2 = 3

Output:

2

Explanation:

2 is the lowest node that is an ancestor of both 1 and 3.

Constraints:

  • $(1 \leq \text{Number of Nodes} \leq 10^5)$
  • $(1 \leq \text{node->data} \leq 10^5)$
  • $(1 \leq \text{Node Value}, n1, n2 \leq 10^5)$

🎯 My Approach:

Iterative Approach (O(H) Time, O(1) Space)

  1. Start from the root of the BST.
  2. If root->data is greater than both n1 and n2, move to the left subtree.
  3. If root->data is smaller than both n1 and n2, move to the right subtree.
  4. Otherwise, return root as it is the Lowest Common Ancestor (LCA).

Algorithm Steps:

  1. Start at the root node.
  2. While root is not NULL:
    • If root->data > max(n1, n2), move left.
    • If root->data < min(n1, n2), move right.
    • Otherwise, root is the LCA, return it.

🕒 Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(H), where H is the height of the BST. In a balanced BST, H = log N, so this is efficient.
  • Expected Auxiliary Space Complexity: O(1), as no additional data structures are used.

📝 Solution Code

Code (C++)

class Solution {
public:
    Node* LCA(Node* root, Node* n1, Node* n2) {
        while (root && (root->data > max(n1->data, n2->data) || root->data < min(n1->data, n2->data)))
            root = (root->data > n1->data) ? root->left : root->right;
        return root;
    }
};

🌲 Alternative Approaches

1️⃣ Recursive Approach (O(H) Time, O(H) Space)

  • Base case: If root is NULL, return NULL.
  • If both n1 and n2 are smaller, move left.
  • If both n1 and n2 are greater, move right.
  • Otherwise, return root, as it's the LCA.
class Solution {
public:
    Node* LCA(Node* root, Node* n1, Node* n2) {
        if (!root || root->data == n1->data || root->data == n2->data) return root;
        if (root->data > n1->data && root->data > n2->data) return LCA(root->left, n1, n2);
        if (root->data < n1->data && root->data < n2->data) return LCA(root->right, n1, n2);
        return root;
    }
};

🔹 Pros: Simple and easy to understand.
🔹 Cons: Uses recursion stack space (O(H)).

2️⃣ Iterative Approach Using Stack (O(H) Time, O(H) Space)

  • Mimics recursion using an explicit stack.
  • Instead of recursive calls, we use a while loop and a stack.
class Solution {
public:
    Node* LCA(Node* root, Node* n1, Node* n2) {
        stack<Node*> st;
        while (root) {
            if (root->data > n1->data && root->data > n2->data) root = root->left;
            else if (root->data < n1->data && root->data < n2->data) root = root->right;
            else return root;
        }
        return nullptr;
    }
};

🔹 Pros: Avoids function call stack overflow.
🔹 Cons: Slightly more complex than recursion.

📊 Comparison of Approaches

Approach ⏱️ Time Complexity 🗂️ Space Complexity ⚡ Method ✅ Pros ⚠️ Cons
Optimized Iterative 🟢 O(H) 🟢 O(1) Iterative Best runtime and space efficiency None
Recursive 🟢 O(H) 🟡 O(H) Recursion Simple and readable Uses recursion stack space
Iterative (Stack) 🟢 O(H) 🟢 O(1) Iterative Mimics recursion without function calls Slightly complex implementation

💡 Best Choice?

  • ✅ For best efficiency: Optimized Iterative Approach (O(1) space, O(H) time).
  • ✅ For simplicity: Recursive approach.
  • ✅ For avoiding recursion depth issues: Iterative (Stack-based) approach.

Code (Java)

class Solution {
    Node LCA(Node root, Node n1, Node n2) {
        while (root != null && (root.data > Math.max(n1.data, n2.data) || root.data < Math.min(n1.data, n2.data)))
            root = (root.data > n1.data) ? root.left : root.right;
        return root;
    }
}

Code (Python)

class Solution:
    def LCA(self, root, n1, n2):
        while root and (root.data > max(n1.data, n2.data) or root.data < min(n1.data, n2.data)):
            root = root.left if root.data > n1.data else root.right
        return root

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count