235. Lowest Common Ancestor of a Binary Search Tree — LeetCode(Python)

I got you!

Problem:

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.

Solution:

1. Iterative Approach —

Explanation —

If both p and q nodes have values smaller than the current node, we traverse only the left subtree.

If both p and q nodes have values greater than the current node, we traverse only the right subtree.

If, however, we find a node which has a value that is in between the values of both p and q nodes, we have found the split condition and thus have found the lowest common ancestor.

Time and Space Complexity —

One more way to think of it is that at every iteration, we divide the tree into two equal halves — left and right. So we are dividing n nodes into two halves until we reach a given node. In the worst case, we exhaust to only one node remaining in the tree. How many times can we divide n to get to 1?

log(n)

Also, we require a constant amount of auxiliary space to solve this problem.

Thus, if n is the number of nodes in the tree.

Time Complexity: O(log(n))

Space Complexity: O(1)

2. Recursive Approach —

Explanation —

Instead of shifting our root to the left or right subtree, we recurse on the left or right subtree whenever necessary.

And in the case that we do not need to recurse on either subtree, we return the root itself, which is our lowest common ancestor.

Time and Space Complexity —

The space complexity, however, is not constant now because of the recursion stack. The auxiliary space required now is also logarithmic since it depends on the height of the tree.

Thus, if n is the number of nodes in the binary tree,

Time Complexity: O(log(n))

Space Complexity: O(log(n))

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store