👵235. Lowest Common Ancestor of a Binary Search Tree

Easy | Grind 75 | August 27 Saturday, 2022

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).”

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.

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.

Second Tab

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

SOLUTION

Binary Search Tree VS Binary Tree

• Binary Tree A binary tree is a tree data structure whereby ever node has at most 2 node child.

• Binary Search Tree: is a sorted binary tree. Ever node is bigger than its left subtree but smaller than its right subtree.

We know that if the current node we are looking at is smaller than both p and q, we need to search the right subtree because thats the only place where we can find p and q. Similarly, we only search it's left subtree when the current node is greater than p and q. If the current node is larger than p and smaller than q or vice versa, then the current node is our LCA because this is where the path for p and q diverges. If the current node is either p or q, we directly return the current node.

CODE: the code is exactly as the explanation above. We use recursion to traverse the tree. If the root node is smaller than both p and q, we traverse the tree with root.right as the root. If the root is bigger than both p and q, we traverse the tree with root.left as the root. We repeat this until the path diverges or the root node is equal to p or q.

n# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # root value is greater than both p and q, check the left side of the root
        if p.val < root.val and q.val < root.val: 
            return self.lowestCommonAncestor(root.left, p, q)
        
        # root value is smaller than both p and q, check the right side of the root
        elif p.val > root.val and q.val > root.val: 
            return self.lowestCommonAncestor(root.right, p, q)
        
        # the tree diverges in terms of p and q here. 
        else:
            return root

TIME AND SPACE COMPLEXITY

TIME: O(logn) where n is the number of nodes. Every time we traverse, we either take the left or right subtree. In doing that, we eliminate half of the search space.

SPACE: O(1) we do not store anything.