Lowest common ancestor of a binary search tree#

Levels: level-2

Data structures: tree

Practice Link#

LeetCode

Description#

Given a binary search tree (BST), find the lowest common ancestor (LCA) 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).”

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

Examples#

1Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
2Output: 6
3Explanation: The LCA of nodes 2 and 8 is 6.

1Output: 2
2Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Python Solution#

 1class TreeNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.left = None
 5        self.right = None
 6
 7
 8class Solution:
 9    # Recursive solution is O(N) in time and O(N) in space
10    def lowestCommonAncestorRecursive(self, root, p, q):
11        """
12        :type root: TreeNode
13        :type p: TreeNode
14        :type q: TreeNode
15        :rtype: TreeNode
16        """
17        # Value of current node or parent node.
18        parent_val = root.val
19
20        # Value of p
21        p_val = p.val
22
23        # Value of q
24        q_val = q.val
25
26        # If both p and q are greater than parent
27        if p_val > parent_val and q_val > parent_val:
28            return self.lowestCommonAncestorRecursive(root.right, p, q)
29        # If both p and q are lesser than parent
30        elif p_val < parent_val and q_val < parent_val:
31            return self.lowestCommonAncestorRecursive(root.left, p, q)
32        # We have found the split point, i.e. the LCA node.
33        else:
34            return root
35
36    # Iterative solution is O(N) in time and O(1) in space
37    def lowestCommonAncestorIterative(self, root, p, q):
38        """
39        :type root: TreeNode
40        :type p: TreeNode
41        :type q: TreeNode
42        :rtype: TreeNode
43        """
44
45        # Value of p
46        p_val = p.val
47
48        # Value of q
49        q_val = q.val
50
51        # Start from the root node of the tree
52        node = root
53
54        # Traverse the tree
55        while node:
56
57            # Value of current node or parent node.
58            parent_val = node.val
59
60            if p_val > parent_val and q_val > parent_val:
61                # If both p and q are greater than parent
62                node = node.right
63            elif p_val < parent_val and q_val < parent_val:
64                # If both p and q are lesser than parent
65                node = node.left
66            else:
67                # We have found the split point, i.e. the LCA node.
68                return node