algoadvance

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Problem Statement

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 T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

For example, given the following BST:

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3  5

Clarifying Questions

  1. Input Constraints:
    • Can we assume that both p and q are present in the BST?
    • Are node values unique?
  2. Node Definition:
    • What is the structure of the tree node? Typically, for BST problems on LeetCode, each node is defined as: 
      struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Strategy

For a BST, we can make use of the properties that the left subtree contains nodes with values less than the root’s value, and the right subtree contains nodes with values greater than the root’s value. This helps in efficiently finding the LCA with the following approach:

  1. Start from the root node.
  2. If both p and q are greater than the root, then LCA is in the right subtree.
  3. If both p and q are less than the root, then LCA is in the left subtree.
  4. If one is on the left and the other is on the right, or one of them is equal to the root, then the root is the LCA.

Code

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Start from the root node of the BST
        while (root != NULL) {
            // If both p and q are greater than root, LCA is in the right subtree
            if (p->val > root->val && q->val > root->val) {
                root = root->right;
            }
            // If both p and q are less than root, LCA is in the left subtree
            else if (p->val < root->val && q->val < root->val) {
                root = root->left;
            }
            // If one is on the left and the other is on the right, root is LCA
            else {
                return root;
            }
        }
        return NULL; // This line is never reached if p and q are guaranteed to be in the BST.
    }
};

Time Complexity

The time complexity of this approach is O(h), where h is the height of the BST. In the best case, this is O(log n) for a balanced BST, and in the worst case, this is O(n) for a skewed BST (where n is the number of nodes in the tree).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI