Jobs

Interviews

Discussions

Lowest Common Ancestor of a Binary Search Tree

Medium

Asked by:

More companies

174 views

Topics:

TreesBinary Search

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, 10⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q will exist in the BST.

Try coding it in LeetCode

Lowest Common Ancestor of a Binary Search Tree

Medium

Asked by:

174 views

Topics:

TreesBinary Search

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

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⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q will exist in the BST.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are both nodes `p` and `q` guaranteed to exist within the BST?
What should be returned if `p` or `q` is the root node itself?
Can we assume that `p` and `q` are distinct nodes?
Are the values of the nodes in the BST guaranteed to be unique?
What is the range of values for the node values in the BST?

Brute Force Solution

Approach

The brute-force way to find the lowest common ancestor in a binary search tree involves exploring all possible ancestor candidates. We essentially check every node in the tree to see if it is an ancestor of both of our target nodes. It’s like trying every single suspect in a mystery until you find the culprit.

Here's how the algorithm would work step-by-step:

Look at each node in the tree, one at a time.
For the current node being examined, check if it is an ancestor of both of the target nodes we are interested in.
To check if the current node is an ancestor, see if both target nodes exist in the subtree rooted at the current node.
If the current node is an ancestor of both target nodes, keep it in mind as a possible lowest common ancestor.
As we continue looking at more nodes, if we find another node that is also an ancestor of both target nodes, and this node is lower in the tree than our previous best guess, replace our best guess with this new node.
Continue this process until all the nodes in the tree have been considered.
The last node that was identified as an ancestor of both target nodes, and that is located deepest in the tree, is the lowest common ancestor.

Code Implementation

def lowest_common_ancestor_brute_force(root, first_node, second_node):
    lowest_common_ancestor = None

    def is_ancestor(potential_ancestor, target_node):
        if potential_ancestor is None:
            return False
        if potential_ancestor == target_node:
            return True

        return is_ancestor(potential_ancestor.left, target_node) or \
               is_ancestor(potential_ancestor.right, target_node)

    def check_node_is_lca(node):
        nonlocal lowest_common_ancestor

        # See if current node is ancestor of both nodes.
        if is_ancestor(node, first_node) and is_ancestor(node, second_node):

            # Update lowest ancestor if current is lower
            if lowest_common_ancestor is None:
                lowest_common_ancestor = node
            elif get_depth(node) > get_depth(lowest_common_ancestor):
                lowest_common_ancestor = node

    def get_depth(node):
        if node is None:
            return 0
        depth = 0
        current = root

        #Traverse down to the node, incrementing depth
        while(current != node):
            if(node.val < current.val):
                current = current.left
            else:
                current = current.right
            depth += 1
        return depth

    def traverse(node):
        if node is not None:
            check_node_is_lca(node)
            traverse(node.left)
            traverse(node.right)

    #Iterate every node, looking for suitable ancestor
    traverse(root)
    return lowest_common_ancestor

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each of the n nodes in the Binary Search Tree. For each node, we perform a check to see if it's an ancestor of both target nodes. This ancestor check involves traversing the subtree rooted at the current node to find the target nodes. In the worst case, this subtree traversal can take O(n) time, particularly if the subtree encompasses a significant portion of the BST. Therefore, the overall time complexity is O(n * n), which simplifies to O(n^2).

Space Complexity

O(1) – The brute-force algorithm checks each node in the tree and uses a constant amount of extra space to store temporary variables. It keeps track of the current node being examined and the current best guess for the lowest common ancestor. No auxiliary data structures that scale with the input size N (the number of nodes in the tree) are required; the algorithm only uses a few constant-size variables to hold the current node and best guess. Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find the shared ancestor that is closest to two specific nodes in a binary search tree. Instead of searching randomly, we will use the properties of the binary search tree to efficiently navigate toward the answer.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root node).
Compare the values of the two nodes we're looking for with the value of the current node.
If both nodes' values are smaller than the current node's value, it means the lowest common ancestor must be somewhere in the left side of the tree. Go left.
If both nodes' values are larger than the current node's value, the lowest common ancestor must be somewhere in the right side of the tree. Go right.
If one node's value is smaller and the other is larger than the current node's value, or if either of the target nodes is equal to the current node's value, we have found the lowest common ancestor. It's the current node.
Repeat steps 2-5 until the lowest common ancestor is found.

Code Implementation

def lowest_common_ancestor(root_node, node_p, node_q):
    current_node = root_node

    while current_node:
        # If both nodes are smaller, LCA is in the left subtree.
        if node_p.val < current_node.val and node_q.val < current_node.val:
            current_node = current_node.left

        # If both nodes are larger, LCA is in the right subtree.
        elif node_p.val > current_node.val and node_q.val > current_node.val:
            current_node = current_node.right

        # Current node is the LCA.
        else:
            return current_node

Big(O) Analysis

Time Complexity

O(log n) – The algorithm traverses the binary search tree from the root towards the target nodes p and q. In each step, it compares the values of p and q with the current node's value to decide whether to go left or right. Because it's a binary search tree, each comparison effectively halves the search space. Therefore, in the worst-case scenario, the number of steps is proportional to the height of the tree, which is log n for a balanced binary search tree, where n is the number of nodes.

Space Complexity

O(1) – The algorithm described uses an iterative approach to traverse the Binary Search Tree. It only stores a constant number of variables, such as the current node being visited, and does not create any auxiliary data structures that scale with the input size, N, where N is the number of nodes in the BST. Therefore, the auxiliary space used remains constant, regardless of the tree's size. The space complexity is O(1).

Edge Cases

Case	How to Handle
Root is null	Return null if the root is null, as there is no tree.
p or q is null	Throw an IllegalArgumentException because the search nodes should exist.
p and q are the same node	Return p (or q) as it is the lowest common ancestor of itself.
p or q is not in the tree	The problem statement typically assumes that p and q are in the tree, so handle it by returning null or throwing an exception, depending on requirements.
p is an ancestor of q	The algorithm should correctly identify p as the LCA.
q is an ancestor of p	The algorithm should correctly identify q as the LCA.
Large BST with deeply nested nodes	The iterative approach scales efficiently as it avoids recursion overhead, preventing stack overflow errors.
BST with skewed distribution (e.g., all nodes on one side)	The algorithm should still correctly find the LCA, potentially with slightly higher time complexity depending on the path to p and q, but not impacting correctness.

Root is null

How to Handle:

Return null if the root is null, as there is no tree.

p or q is null

How to Handle:

Throw an IllegalArgumentException because the search nodes should exist.

p and q are the same node

How to Handle:

Return p (or q) as it is the lowest common ancestor of itself.

p or q is not in the tree

How to Handle:

The problem statement typically assumes that p and q are in the tree, so handle it by returning null or throwing an exception, depending on requirements.

p is an ancestor of q

How to Handle:

The algorithm should correctly identify p as the LCA.

q is an ancestor of p

How to Handle:

The algorithm should correctly identify q as the LCA.

Large BST with deeply nested nodes

How to Handle:

The iterative approach scales efficiently as it avoids recursion overhead, preventing stack overflow errors.

BST with skewed distribution (e.g., all nodes on one side)

How to Handle:

The algorithm should still correctly find the LCA, potentially with slightly higher time complexity depending on the path to p and q, but not impacting correctness.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are both nodes `p` and `q` guaranteed to exist within the BST?
What should be returned if `p` or `q` is the root node itself?
Can we assume that `p` and `q` are distinct nodes?
Are the values of the nodes in the BST guaranteed to be unique?
What is the range of values for the node values in the BST?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each node in the tree, one at a time.
For the current node being examined, check if it is an ancestor of both of the target nodes we are interested in.
To check if the current node is an ancestor, see if both target nodes exist in the subtree rooted at the current node.
If the current node is an ancestor of both target nodes, keep it in mind as a possible lowest common ancestor.
As we continue looking at more nodes, if we find another node that is also an ancestor of both target nodes, and this node is lower in the tree than our previous best guess, replace our best guess with this new node.
Continue this process until all the nodes in the tree have been considered.
The last node that was identified as an ancestor of both target nodes, and that is located deepest in the tree, is the lowest common ancestor.

Code Implementation

def lowest_common_ancestor_brute_force(root, first_node, second_node):
    lowest_common_ancestor = None

    def is_ancestor(potential_ancestor, target_node):
        if potential_ancestor is None:
            return False
        if potential_ancestor == target_node:
            return True

        return is_ancestor(potential_ancestor.left, target_node) or \
               is_ancestor(potential_ancestor.right, target_node)

    def check_node_is_lca(node):
        nonlocal lowest_common_ancestor

        # See if current node is ancestor of both nodes.
        if is_ancestor(node, first_node) and is_ancestor(node, second_node):

            # Update lowest ancestor if current is lower
            if lowest_common_ancestor is None:
                lowest_common_ancestor = node
            elif get_depth(node) > get_depth(lowest_common_ancestor):
                lowest_common_ancestor = node

    def get_depth(node):
        if node is None:
            return 0
        depth = 0
        current = root

        #Traverse down to the node, incrementing depth
        while(current != node):
            if(node.val < current.val):
                current = current.left
            else:
                current = current.right
            depth += 1
        return depth

    def traverse(node):
        if node is not None:
            check_node_is_lca(node)
            traverse(node.left)
            traverse(node.right)

    #Iterate every node, looking for suitable ancestor
    traverse(root)
    return lowest_common_ancestor

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root node).
Compare the values of the two nodes we're looking for with the value of the current node.
If both nodes' values are smaller than the current node's value, it means the lowest common ancestor must be somewhere in the left side of the tree. Go left.
If both nodes' values are larger than the current node's value, the lowest common ancestor must be somewhere in the right side of the tree. Go right.
If one node's value is smaller and the other is larger than the current node's value, or if either of the target nodes is equal to the current node's value, we have found the lowest common ancestor. It's the current node.
Repeat steps 2-5 until the lowest common ancestor is found.

Code Implementation

def lowest_common_ancestor(root_node, node_p, node_q):
    current_node = root_node

    while current_node:
        # If both nodes are smaller, LCA is in the left subtree.
        if node_p.val < current_node.val and node_q.val < current_node.val:
            current_node = current_node.left

        # If both nodes are larger, LCA is in the right subtree.
        elif node_p.val > current_node.val and node_q.val > current_node.val:
            current_node = current_node.right

        # Current node is the LCA.
        else:
            return current_node

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Root is null	Return null if the root is null, as there is no tree.
p or q is null	Throw an IllegalArgumentException because the search nodes should exist.
p and q are the same node	Return p (or q) as it is the lowest common ancestor of itself.
p or q is not in the tree	The problem statement typically assumes that p and q are in the tree, so handle it by returning null or throwing an exception, depending on requirements.
p is an ancestor of q	The algorithm should correctly identify p as the LCA.
q is an ancestor of p	The algorithm should correctly identify q as the LCA.
Large BST with deeply nested nodes	The iterative approach scales efficiently as it avoids recursion overhead, preventing stack overflow errors.
BST with skewed distribution (e.g., all nodes on one side)	The algorithm should still correctly find the LCA, potentially with slightly higher time complexity depending on the path to p and q, but not impacting correctness.

Root is null

How to Handle:

Return null if the root is null, as there is no tree.

p or q is null

How to Handle:

Throw an IllegalArgumentException because the search nodes should exist.

p and q are the same node

How to Handle:

Return p (or q) as it is the lowest common ancestor of itself.

p or q is not in the tree

How to Handle:

The problem statement typically assumes that p and q are in the tree, so handle it by returning null or throwing an exception, depending on requirements.

p is an ancestor of q

How to Handle:

The algorithm should correctly identify p as the LCA.

q is an ancestor of p

How to Handle:

The algorithm should correctly identify q as the LCA.

Large BST with deeply nested nodes

How to Handle:

The iterative approach scales efficiently as it avoids recursion overhead, preventing stack overflow errors.

BST with skewed distribution (e.g., all nodes on one side)

How to Handle:

The algorithm should still correctly find the LCA, potentially with slightly higher time complexity depending on the path to p and q, but not impacting correctness.