Practice/LinkedIn/Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

CodingMust

Problem

You are given the root of a binary search tree (BST) and two integer values representing nodes p and q that exist in the tree. Your task is to find and return the value of the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor is defined as the deepest node in the tree that has both p and q as descendants. Note that a node is considered a descendant of itself, so if one of the target nodes is an ancestor of the other, that node is the LCA.

Remember that in a binary search tree, for every node:

• All values in the left subtree are less than the node's value
• All values in the right subtree are greater than the node's value

Requirements

1. Return the value of the lowest common ancestor node
2. Both p and q are guaranteed to exist in the tree
3. All node values in the tree are unique
4. Utilize the BST property to optimize your solution

Constraints

• The number of nodes in the tree is in the range [2, 100,000]
• -1,000,000,000 ≤ Node.val ≤ 1,000,000,000
• All Node.val are unique
• p ≠ q
• Both p and q exist in the BST

Examples

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. Node 2 is in the left subtree and node 8 is in the right subtree of node 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 an ancestor of itself. Node 4 is a descendant of node 2.

Example 3:

Input: root = [10,5,15,3,7,null,20], p = 3, q = 7 Output: 5 Explanation: Both nodes 3 and 7 are in the left subtree, and their LCA is node 5.