235. Lowest Common Ancestor of a Binary Search Tree LeetCode Solution

In this guide, you will get 235. Lowest Common Ancestor of a Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Lowest Common Ancestor of a Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Lowest Common Ancestor of a Binary Search Tree solution in C++
4. Lowest Common Ancestor of a Binary Search Tree solution in Java
5. Lowest Common Ancestor of a Binary Search Tree solution in Python
6. Additional Resources

Problem Statement of 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).”

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, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the BST.

Complexity Analysis

• Time Complexity: O(h)
• Space Complexity: O(h)

235. Lowest Common Ancestor of a Binary Search Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root->val > max(p->val, q->val))
      return lowestCommonAncestor(root->left, p, q);
    if (root->val < min(p->val, q->val))
      return lowestCommonAncestor(root->right, p, q);
    return root;
  }
};
/* code provided by PROGIEZ */

235. Lowest Common Ancestor of a Binary Search Tree LeetCode Solution in Java

class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > Math.max(p.val, q.val))
      return lowestCommonAncestor(root.left, p, q);
    if (root.val < Math.min(p.val, q.val))
      return lowestCommonAncestor(root.right, p, q);
    return root;
  }
}
// code provided by PROGIEZ

235. Lowest Common Ancestor of a Binary Search Tree LeetCode Solution in Python

class Solution:
  def lowestCommonAncestor(
      self,
      root: 'TreeNode',
      p: 'TreeNode',
      q: 'TreeNode',
  ) -> 'TreeNode':
    if root.val > max(p.val, q.val):
      return self.lowestCommonAncestor(root.left, p, q)
    if root.val < min(p.val, q.val):
      return self.lowestCommonAncestor(root.right, p, q)
    return root
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.