235. Lowest Common Ancestor of a Binary Search Tree

Description

Given a binary search tree (BST) and two nodes, p and q, find their lowest common ancestor (LCA). The LCA of two nodes p and q in a BST is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Intuition

In a binary search tree, for any given node N, all the nodes in the left subtree of N have values less than N.val, and all the nodes in the right subtree of N have values greater than N.val. This property allows us to efficiently find the LCA by navigating the tree based on the values of p and q.

• If both p and q are smaller than N, then their LCA must be in the left subtree.
• If both p and q are greater than N, then their LCA must be in the right subtree.
• If p and q are on different sides of N, or if one of them is equal to N, then N is the LCA.

Approach

1. Start at the root of the tree.
2. Traverse the tree based on the values of p and q: - If both p and q are smaller than the current node's value, move to the left child. - If both p and q are greater than the current node's value, move to the right child. - If p and q are on different sides, or if one of them matches the current node, then the current node is the LCA.
3. Return the current node as the LCA.

Complexity

Time Complexity:

O(h), where h is the height of the tree. In the worst case, the algorithm may need to traverse from the root to a leaf node, which would take h steps.

Space Complexity:

O(1), since the solution only uses a constant amount of extra space.

Code

C++

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (root->val < p->val && root->val < q->val) {
                root = root->right;
            }
            else if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } else {
                break;
            }
        }
        return root;
    }
};

Python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        while root:
            if root.val < p.val and root.val < q.val:
                root = root.right
            elif root.val > p.val and root.val > q.val:
                root = root.left
            else:
                break
        return root

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else {
                break;
            }
        }
        return root;
    }
}

JavaScript

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
    if (!root) return null;
    while (root) {
        if (root.val < p.val && root.val < q.val) {
            root = root.right;
        }
        else if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else {
            break;
        }
    }
    return root;
};