235. Lowest Common Ancestor of a Binary Search Tree

Description

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).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 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: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

The number of nodes in the tree is in the range [2, 10⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q will exist in the BST.

Solutions

Solution 1: Iteration

Thinking

In a BST the LCA of \(p\) and \(q\) is the fork between their values. Walk from the root: go left if both are smaller, right if both are larger, otherwise the current node is the fork.

The walk is iterative and needs no call stack.

Starting from the root node, we traverse the tree. If the current node's value is less than both \(\textit{p}\) and \(\textit{q}\) values, it means that \(\textit{p}\) and \(\textit{q}\) should be in the right subtree of the current node, so we move to the right child. If the current node's value is greater than both \(\textit{p}\) and \(\textit{q}\) values, it means that \(\textit{p}\) and \(\textit{q}\) should be in the left subtree, so we move to the left child. Otherwise, it means the current node is the lowest common ancestor of \(\textit{p}\) and \(\textit{q}\), so we return the current node.

The time complexity is \(O(n)\), where \(n\) is the number of nodes in the binary search tree. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptC#

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


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

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (true) {
            if (root.val < Math.min(p.val, q.val)) {
                root = root.right;
            } else if (root.val > Math.max(p.val, q.val)) {
                root = root.left;
            } else {
                return root;
            }
        }
    }
}

/**
 * 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) {
        while (1) {
            if (root->val < min(p->val, q->val)) {
                root = root->right;
            } else if (root->val > max(p->val, q->val)) {
                root = root->left;
            } else {
                return root;
            }
        }
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for {
        if root.Val < min(p.Val, q.Val) {
            root = root.Right
        } else if root.Val > max(p.Val, q.Val) {
            root = root.Left
        } else {
            return root
        }
    }
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode | null,
    q: TreeNode | null,
): TreeNode | null {
    while (root) {
        if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else if (root.val < p.val && root.val < q.val) {
            root = root.right;
        } else {
            return root;
        }
    }
}

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

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (true) {
            if (root.val < Math.Min(p.val, q.val)) {
                root = root.right;
            } else if (root.val > Math.Max(p.val, q.val)) {
                root = root.left;
            } else {
                return root;
            }
        }
    }
}

Solution 2: Recursion

Thinking

The same fork rule is a recursion: recurse into the side that contains both, otherwise return the current root. The idea matches the iteration with a shorter implementation.

We can also use a recursive approach to solve this problem.

We first check if the current node's value is less than both \(\textit{p}\) and \(\textit{q}\) values. If it is, we recursively traverse the right subtree. If the current node's value is greater than both \(\textit{p}\) and \(\textit{q}\) values, we recursively traverse the left subtree. Otherwise, it means the current node is the lowest common ancestor of \(\textit{p}\) and \(\textit{q}\), so we return the current node.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the number of nodes in the binary search tree.