Lowest Common Ancestor Of A Binary Search Tree Leetcode Problem [Python]

In this blog post, we're going to tackle the Lowest Common Ancestor Of A Binary Search Tree problem, which is problem number 235 on LeetCode.

This problem falls under the category of trees and is rated as medium in terms of difficulty.

We'll provide a Python solution to solve this problem efficiently.

Problem Overview

The problem statement is as follows: 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 the tree that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Example:

Let's consider a couple of examples to better understand the problem:

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^5].
• -10^9 <= Node.val <= 10^9
• All Node.val values are unique.
• p is not equal to q.
• p and q will exist in the BST.

Understanding the Constraints

Before diving into the solution, let's discuss the constraints associated with this problem.

1. The number of nodes in the tree can be as large as 10^5. This means that our solution needs to be efficient and not have a time complexity of O(n), where n is the number of nodes in the tree.

2. The values of the nodes in the tree can range from -10^9 to 10^9. This is essential to know, as it affects the way we compare node values.

3. All node values are unique, which simplifies the process of identifying nodes in the tree.

4. The nodes p and q are distinct and will exist in the BST.

This guarantees that we won't have to handle edge cases where p or q is missing.

Lowest Common Ancestor of a Binary Search Tree LeetCode Problem Solution

To find the lowest common ancestor of two nodes p and q in a binary search tree efficiently, we can use a straightforward iterative approach.

The key insight is that the LCA will be the first node at which we encounter a split between the paths to p and q in the tree.

Here's the Python solution to the problem:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def lowestCommonAncestor(root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
    while root:
        if root.val < p.val and root.val < q.val:
            root = root.right
        elif root.val > p.val and root.val > q.val:
            root = root.left
        else:
            return root

Let's break down the solution:

• We start at the root node, as it is always a common ancestor of every node in the tree.

• We iterate through the tree until we find the lowest common ancestor.

This iterative approach allows us to find the LCA efficiently without visiting every node in the tree.

• In each iteration, we check the values of the current node root and the values of p and q.

• If both p and q are greater than the current node's value, we move to the right subtree, as both p and q must be in the right subtree to find the LCA.

• If both p and q are less than the current node's value, we move to the left subtree, as both p and q must be in the left subtree to find the LCA.

• If the above conditions are not met, it means we have found the LCA, and we return the current node as the result.

This solution has a time complexity of O(log n) on average, where n is the number of nodes in the binary search tree.

The reason for this is that we effectively prune half of the tree with each iteration, making it a logarithmic time complexity.

The space complexity is O(1) as we do not use any additional data structures.

Reasoning Behind Our Approach

The reasoning behind this efficient approach is quite straightforward.

Since the given binary search tree (BST) has a specific structure where nodes on the left are smaller than their parent nodes, and nodes on the right are greater than their parent nodes, we can leverage this structure to quickly find the lowest common ancestor.

As we traverse the tree from the root, we continuously compare the values of the current node with p and q.

The key insight is that when we encounter a node whose value is between p and q, it means we have found the split point, and that node is the lowest common ancestor.

Let's illustrate this with an example.

Suppose p = 2 and q = 8, and we start at the root, which has a value of 6.

Here's what happens during the traversal:

1. We compare 6 (current node) with 2 and 8.

Since both 2 and 8 are greater than 6, we move to the right subtree.
2. In the right subtree, we compare 8 (current node) with 2 and 8.

Now, 8 is greater than 6, so we continue moving in the right subtree.
3. We reach a point where the current node's value is between 2 and 8.

This is the split point, and we have found the lowest common ancestor, which is 6.

This approach is efficient because it eliminates the need to explore the entire tree.

Instead, we quickly narrow down our search to the correct subtree based on the values of p and q.

Time and Space Complexity

Let's analyze the time and space complexity of our solution.

Time Complexity:

The time complexity of our solution is O(log n) on average, where n is the number of nodes in the binary search tree.

This is because, in each iteration, we effectively prune half of the tree by moving to either the left or right subtree.

As a result, the number of nodes we need

to visit is logarithmic in the size of the tree.

Space Complexity:

The space complexity is O(1) because we do not use any additional data structures that grow with the input.

We only use a constant amount of space to keep track of the current node and the input values.

Related Interview Questions By Company:

• Target Sum LeetCode
• Subsets LeetCode
• Coin Change II LeetCode

Related Interview Questions By Difficulty:

• Delete Node In A BST LeetCode
• Path Sum LeetCode
• Binary Tree Preorder Traversal LeetCode

Related Interview Questions By Category:

• Shortest Path In Binary Matrix LeetCode
• Count Vowels Permutation LeetCode
• Find K Closest Elements LeetCode

Conclusion

In this blog post, we tackled the Lowest Common Ancestor Of A Binary Search Tree problem, which is problem number 235 on LeetCode.

We provided an efficient Python solution that leverages the properties of binary search trees to find the lowest common ancestor of two given nodes p and q.

By comparing the values of the nodes during traversal, we can quickly identify the split point and return the lowest common ancestor.

Understanding and efficiently solving tree-related problems like this one is a valuable skill for coding interviews and real-world applications.

We hope this explanation and solution have been helpful to you.

If you have any questions, comments, or suggestions, please feel free to leave them below.

We encourage you to engage with the content and share your thoughts.

Additionally, if you found this post valuable, please like and engage for more coding and problem-solving content.

For the original problem statement and more details, you can refer to the LeetCode problem description.

Happy coding!