235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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).”

Approach 1:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        if (root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

The "Lowest Common Ancestor (LCA) of a Binary Search Tree (BST)" problem is a fundamental tree problem. The goal is to find the LCA of two nodes in a BST. In a BST, for any node, all nodes in its left subtree are smaller, and all nodes in its right subtree are larger. This property can be leveraged to efficiently find the LCA.

The LCA of two nodes in a tree is defined as the lowest node that is an ancestor of both nodes. The problem specifically asks for the LCA of two nodes in a BST.

Problem Statement

Given a binary search tree, find the lowest common ancestor of two given nodes in the BST. The BST is defined as:

The binary search tree is represented by a tree node structure, and you are required to find the LCA of the two given nodes.

Approach

The key observation in this problem is that, in a binary search tree:

• If both nodes are smaller than the current node, then the LCA must be in the left subtree.
• If both nodes are larger than the current node, then the LCA must be in the right subtree.
• If one node is smaller and the other is larger, the current node is their lowest common ancestor.

This property allows us to solve the problem in a very efficient manner without needing to traverse the entire tree.

Algorithm

The algorithm to find the LCA of two nodes in a BST can be described as follows:

• Start at the root node.
• If both target nodes are smaller than the current node, then move to the left child.
• If both target nodes are larger than the current node, then move to the right child.
• If one target node is smaller and the other is larger, then the current node is the LCA.
• Continue this process until the LCA is found.

Example

Let's consider an example where we need to find the LCA of nodes 2 and 8 in the following BST:

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

- The nodes 2 and 8 are on opposite sides of the root node (6). Thus, the LCA of 2 and 8 is 6.

- If we were to find the LCA of nodes 2 and 4, the LCA would be 2 because both nodes are in the left subtree of the root.

Code Implementation

Below is a Python implementation of the algorithm that finds the LCA of two nodes in a binary search tree:

- We start from the root of the tree. - We move to the left or right child based on the values of p and q compared to the current node. - If one of the nodes is smaller and the other is larger, the current node is the LCA. - We return the node when the LCA is found.

Time Complexity

The time complexity of this algorithm is O(h), where h is the height of the tree. In the worst case, we may need to traverse from the root to the leaf nodes. In a balanced BST, this will be O(log n), where n is the number of nodes in the tree. In the worst case (unbalanced tree), the time complexity can be O(n).

The space complexity is O(1), since we are only using a constant amount of space for the traversal (no extra data structures are used).

Conclusion

The "Lowest Common Ancestor of a Binary Search Tree" problem is a common interview question that tests your understanding of binary search trees and their properties. By leveraging the BST property that left nodes are smaller and right nodes are larger, we can efficiently find the LCA without the need for a full tree traversal. This problem highlights the importance of understanding tree structures and how their properties can simplify problem-solving.