Lowest Common Ancestor of a Binary Tree III

Medium

Amazon

3 views

Topics:

Trees

You are given two nodes, p and q, in a binary tree where each node has a pointer to its parent. The structure of each node is defined as follows:

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

Your task is to write a function lowestCommonAncestor(p, q) that finds the lowest common ancestor (LCA) of the two given nodes p and q. The lowest common ancestor is defined as the deepest node in the tree that is an ancestor of both p and q.

Example:

Consider the following binary tree:

Let's say p is the node with value 5 and q is the node with value 1. The LCA of p and q would be the node with value 3.

Constraints:

The tree may not be balanced.
Each node has a pointer to its parent.
Assume that both nodes p and q are guaranteed to be in the tree.

Could you provide an efficient algorithm to find the LCA of the given nodes and analyze its time and space complexity? Also, please consider edge cases such as when one node is an ancestor of the other or when the nodes are the same.

Lowest Common Ancestor of a Binary Tree III

Medium

Amazon

3 views

Topics:

Trees

You are given two nodes, p and q, in a binary tree where each node has a pointer to its parent. The structure of each node is defined as follows:

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

Your task is to write a function lowestCommonAncestor(p, q) that finds the lowest common ancestor (LCA) of the two given nodes p and q. The lowest common ancestor is defined as the deepest node in the tree that is an ancestor of both p and q.

Example:

Consider the following binary tree:

Let's say p is the node with value 5 and q is the node with value 1. The LCA of p and q would be the node with value 3.

Constraints:

The tree may not be balanced.
Each node has a pointer to its parent.
Assume that both nodes p and q are guaranteed to be in the tree.

Could you provide an efficient algorithm to find the LCA of the given nodes and analyze its time and space complexity? Also, please consider edge cases such as when one node is an ancestor of the other or when the nodes are the same.

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:

Will the input nodes p and q always exist within the binary tree?
Is it possible for either p or q to be the root of the tree?
If p or q is an ancestor of the other, should I return the ancestor node itself?
Can I assume that the parent pointers are correctly maintained for all nodes in the tree?
What should I return if p and q belong to completely disjoint trees (i.e., no common ancestor exists)? Should I return null in this case?

Brute Force Solution

Approach

The brute-force method to find the lowest common ancestor involves tracing the path from each node to the root and then comparing those paths. We aim to find the deepest node that exists on both paths.

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

First, figure out all the ancestors of the first node by walking up the tree from that node to the root. Remember each of these ancestors.
Next, do the same thing for the second node, tracing its path back to the root and keeping track of all its ancestors.
Now, compare the two lists of ancestors you've created. Start from the root and go down.
Find the first node that appears in both ancestor lists. The ancestor closest to the two nodes will be the lowest common ancestor
That node is your answer.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.parent = None

def lowestCommonAncestor(node_one, node_two):
    ancestors_node_one = []
    ancestors_node_two = []

    # Traverse up from node_one to root and store ancestors
    current_node = node_one
    while current_node:
        ancestors_node_one.append(current_node)
        current_node = current_node.parent

    # Traverse up from node_two to root and store ancestors
    current_node = node_two
    while current_node:
        ancestors_node_two.append(current_node)
        current_node = current_node.parent

    # We will compare from the roots down to find the LCA
    lowest_common_ancestor = None
    for ancestor_one in reversed(ancestors_node_one):
        for ancestor_two in reversed(ancestors_node_two):
            if ancestor_one == ancestor_two:

                # Update LCA when common ancestor is found
                lowest_common_ancestor = ancestor_one
                break
        else:
            continue
        break

    return lowest_common_ancestor

Big(O) Analysis

Time Complexity

O(n) – The described algorithm first finds all ancestors of node p by traversing upwards to the root. In the worst case, this could involve traversing all n nodes of the tree. Similarly, it finds all ancestors of node q, which could also take O(n) time. Finally, it compares the two ancestor lists, which again, in the worst case, could require comparing all n ancestors. Since these operations happen sequentially, the total time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm creates two lists to store the ancestors of the two input nodes. In the worst-case scenario, where the tree is highly skewed (resembling a linked list), the path from a node to the root could include all N nodes of the tree. Thus, each list of ancestors can grow up to size N, leading to an auxiliary space usage of 2N. Simplifying, the space complexity is O(N).

Optimal Solution

Approach

This problem involves finding the shared ancestor furthest from the two specified nodes in a tree. The key idea is to leverage the parent pointers to trace paths from each node to the root, effectively turning the tree into two linked lists that converge at the lowest common ancestor.

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

Start tracing back from each of the two given nodes, following the parent pointers upwards.
Continue tracing back from both nodes, one step at a time, until the paths intersect.
When the two paths meet, the node where they intersect is the lowest common ancestor of the two original nodes.
If either node reaches the root of the tree without intersecting the other path, continue from the other node until they intersect or also reach the root.
The node where the paths first intersect is the answer.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

def lowestCommonAncestor(first_node, second_node):
    first_node_ancestors = set()

    current_node = first_node
    # Trace first node's path to the root
    while current_node:
        first_node_ancestors.add(current_node)
        current_node = current_node.parent

    current_node = second_node
    # Trace second node's path to the root
    while current_node:
        # Return LCA if the paths intersect
        if current_node in first_node_ancestors:
            return current_node
        current_node = current_node.parent

    return None

Big(O) Analysis

Time Complexity

O(n) – The solution involves traversing upwards from both given nodes to the root of the tree, following parent pointers. In the worst-case scenario, one node might be very deep in the tree while the other is close to the root. Both nodes traverse towards the root, covering a path no longer than the height of the tree, 'h'. Since the height of a binary tree can be, in the worst case, proportional to the number of nodes, 'n', the complexity is bounded by the longer path which is O(n). Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm traces paths from the two given nodes to the root using only parent pointers. No auxiliary data structures like lists or hash maps are created to store visited nodes or path information. Only a few pointer variables (to traverse the paths) are used regardless of the size of the tree (N). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
p and q are the same node	Return p (or q) directly as the LCA since a node is its own ancestor.
Either p or q is null	If either node is null, return the other node; if both are null, return null.
p is an ancestor of q (or vice versa)	The first node encountered while traversing upwards from q (or p) that equals p (or q) is the LCA.
Tree consists of only the nodes p and q, where one is the parent of the other	The parent is the LCA, so the algorithm should correctly identify it during upward traversal.
p and q are siblings (share the same parent)	Traversing upwards from both will lead to their common parent which is the LCA.
p and q are in different subtrees with a distant common ancestor	The algorithm needs to traverse far enough up the tree to reach the common ancestor and should handle potentially long paths efficiently.
One or both of the nodes (p or q) are not actually present in the tree	The upward traversal might reach the root without finding the respective node, indicating that the node isn't in the tree, requiring special return value (e.g., null or an error). We assume the input is valid per problem statement.
The root node has no parent pointer (edge case assumed as the root node should have a null parent)	The algorithm should correctly handle the null parent of the root node during upward traversal.