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

I got you!

Problem:

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.

Solution:

1. Iterative Approach —

Explanation —

This problem has a very trivial solution since the nodes in a binary search tree are arranged in a given way.

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 —

We are only visiting one node per level in the tree, so we can say that our algorithm runs in logarithmic time complexity since it is a function of the height of the tree.

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 —

A similar approach is taken in order to solve this problem recursively.

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 time complexity analysis is the same as above and we can easily conclude that the runtime for our our algorithm is logarithmic.

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:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏