LeetCode #235: Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

To solve the LeetCode problem “Lowest Common Ancestor of a Binary Search Tree,” we need to find the lowest common ancestor of two given nodes in a binary search tree. The binary search tree is a binary tree where the left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree of a node contains only nodes with keys greater than the node’s key. In this post, we will explain how to solve this problem step by step.

Step 1: Check the root node First, we need to check if the root node is null or if either of the given nodes is equal to the root node. If any of these conditions are true, the root node is the lowest common ancestor, so we return the root node.

Step 2: Traverse the tree If the root node is not the lowest common ancestor, we need to traverse the tree to find the lowest common ancestor. We start at the root node and compare the values of the two given nodes with the value of the current node. If both nodes’ values are greater than the current node’s value, we move to the right subtree. If both nodes’ values are less than the current node’s value, we move to the left subtree. If the two nodes’ values are on opposite sides of the current node’s value, we have found the lowest common ancestor, so we return the current node.

Step 3: Return -1 if not found If we have traversed the entire tree and have not found the lowest common ancestor, we return -1.

Here is the Python code that implements the above algorithm:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Check if root is null or either of the given nodes is equal to the root node
        if not root or p == root or q == root:
            return root
        
        # Traverse the tree to find the lowest common ancestor
        node = root
        while node:
            parent_node = node.val
            if p.val > parent_node and q.val > parent_node:
                node = node.right
            elif p.val < parent_node and q.val < parent_node:
                node = node.left
            else:
                return node
        
        # Return -1 if lowest common ancestor not found
        return -1

Time Complexity: The time complexity of this algorithm is O(h), where h is the height of the binary search tree. In the worst case, where the binary search tree is completely unbalanced, the height can be n (the number of nodes), so the time complexity is O(n).

Space Complexity: The space complexity of this algorithm is O(1) because we are only using constant space to store the current node, the two given nodes’ values, and the parent node. Therefore, the space complexity is independent of the size of the input.