Top 5 Interview Problems in Advanced Data Structures and Algorithms (DSA)

Chapter 2: Lowest Common Ancestor (LCA) in a Binary Tree

The Lowest Common Ancestor (LCA) is a fundamental problem in tree-based data structures, commonly asked in coding interviews and competitive programming. The problem involves finding the lowest common ancestor of two nodes in a binary tree. The lowest common ancestor of two nodes is defined as the deepest node that is an ancestor of both nodes.

This problem is a typical tree traversal problem and tests a candidate’s understanding of tree structures, recursive algorithms, and the ability to efficiently navigate between nodes in a tree. The LCA problem has a wide range of applications, including:

• Family tree analysis: Finding the lowest common ancestor of two individuals.
• Graph theory: Understanding connectivity and hierarchical structures.
• File system exploration: Determining the common path between two files or directories.

In this chapter, we will delve into solving the LCA problem for both binary trees and binary search trees (BSTs), covering different approaches and optimizations.

What is a Binary Tree?

A binary tree is a tree data structure where each node has at most two children. These children are referred to as the left child and the right child. A binary tree is typically used to represent hierarchical relationships, where the top node is known as the root, and each subsequent node represents a subproblem or a smaller set of data.

Here is an example of a simple binary tree:

         1

        / \

       2   3

      / \   \

     4   5   6

What is the Lowest Common Ancestor (LCA)?

The Lowest Common Ancestor (LCA) of two nodes ppp and qqq in a tree is defined as the lowest node in the tree that is an ancestor of both ppp and qqq. An ancestor of a node is any node that exists on the path from the root to that node.

For example, in the tree above, the LCA of nodes 4 and 5 is node 2, since node 2 is the lowest node in the tree that has both 4 and 5 as descendants.

1. The Naive Approach to Finding the LCA

A simple brute force approach for finding the LCA involves traversing the entire tree for both nodes and then checking the common nodes between the paths from the root to both nodes. The first common node is the LCA.

Steps of the Naive Approach:

1. Find the path from the root to node ppp.
2. Find the path from the root to node qqq.
3. Compare both paths and find the last common node, which will be the LCA.

However, this approach is inefficient with a time complexity of O(n)O(n)O(n), as it requires searching for paths for both nodes. We can optimize this approach with a more efficient algorithm.

2. Optimized Approach: Using Recursion to Find the LCA

The optimal approach to finding the LCA involves depth-first search (DFS) with recursion. This method eliminates the need to compute paths and instead uses the tree's recursive structure to determine the LCA in O(n) time, where nnn is the number of nodes in the tree.

Recursive Method:

The recursive method works by:

1. Traversing the tree from the root.
2. If the current node is either ppp or qqq, return the current node.
3. If both left and right subtrees return non-null values, it means the current node is the LCA because one node is in the left subtree and the other is in the right subtree.
4. If only one of the subtrees returns a non-null value, propagate that result up the recursion.

Code Sample: Recursive Approach for Finding LCA

class TreeNode:

    def __init__(self, value=0, left=None, right=None):

        self.val = value

        self.left = left

        self.right = right

def lca(root, p, q):

    # Base case: if root is None or root is one of the target nodes

    if root is None or root == p or root == q:

        return root

    # Recursively search in the left and right subtrees

    left = lca(root.left, p, q)

    right = lca(root.right, p, q)

    # If both left and right subtrees have non-null values, root is the LCA

    if left and right:

        return root

    # Otherwise, return the non-null child (either left or right)

    return left if left else right

Explanation:

• We recursively explore the left and right subtrees.
• If both subtrees return non-null values, we know that the current root is the LCA.
• If only one subtree returns a non-null value, it means both nodes are in that subtree, and we return that node.

Time Complexity:

The time complexity is O(n) since each node is visited once.

3. LCA in Binary Search Trees (BSTs)

The LCA problem becomes simpler in a Binary Search Tree (BST) due to the property that, for any node:

• Nodes in the left subtree are smaller than the node.
• Nodes in the right subtree are greater than the node.

This allows us to use the following approach:

1. Start at the root.
2. If both ppp and qqq are smaller than the current node, move to the left child.
3. If both ppp and qqq are larger than the current node, move to the right child.
4. If one node is smaller and the other is larger, the current node is the LCA.

Code Sample: LCA in Binary Search Tree

def lca_bst(root, p, q):

    if root is None:

        return None

    # If both p and q are smaller than root, move to the left child

    if p.val < root.val and q.val < root.val:

        return lca_bst(root.left, p, q)

    # If both p and q are greater than root, move to the right child

    if p.val > root.val and q.val > root.val:

        return lca_bst(root.right, p, q)

    # If one of p or q is on the left and the other on the right, root is the LCA

    return root

Explanation:

• The properties of the BST allow us to skip half of the tree at each step.
• We compare the values of ppp and qqq with the current node’s value and decide whether to move left or right. If one value is smaller and the other is larger, we return the current node as the LCA.

Time Complexity:

• Average Case: O(logn), because we only traverse down the tree once.
• Worst Case:)O(n), if the tree is unbalanced (degenerated to a linked list).

4. Handling Edge Cases in LCA

In the process of solving the LCA problem, it is essential to handle edge cases:

1. Node not present: What if one or both of the nodes do not exist in the tree?
2. LCA is the root: The LCA might be the root of the tree.
3. Single node tree: If the tree contains only one node, the LCA of any two nodes is the root itself.

For these edge cases, we need to ensure that the algorithm returns a valid result, especially when one or both nodes are not present.

Code Sample: Edge Case Handling

def lca_with_edge_cases(root, p, q):

    # Return None if root is None

    if root is None:

        return None

    # If one of the nodes is the root, return the root

    if root == p or root == q:

        return root

    left = lca_with_edge_cases(root.left, p, q)

    right = lca_with_edge_cases(root.right, p, q)

    # If both left and right are non-null, then root is the LCA

    if left and right:

        return root

    # Return the non-null node (either left or right)

    return left if left else right

Explanation:

• The base case checks if the current node is either of the two target nodes or if it's None.
• The rest of the logic remains the same: if both subtrees return non-null values, the current node is the LCA; otherwise, return the non-null child.

5. Applications of LCA

The Lowest Common Ancestor (LCA) problem has a variety of applications in both theoretical and practical domains:

1. Finding common ancestors in family trees.
2. Network routing and pathfinding: LCA is used in networks to determine the common point in a communication path.
3. Data Structures: It is used in Binary Lifting techniques to compute the LCA efficiently for large datasets.

Conclusion

In this chapter, we have:

1. Explored the concept of the Lowest Common Ancestor (LCA) in binary trees.
2. Implemented the recursive approach to find the LCA in both general binary trees and binary search trees (BSTs).
3. Addressed edge cases and optimizations to handle various tree configurations.
4. Discussed the applications of LCA in different domains such as family trees, networks, and data structures.

The LCA problem is crucial for understanding tree structures and recursive algorithms, and mastering it will prepare you for more complex tree-related problems in coding interviews and competitive programming.