Python Coding Test Course, Finding the Lowest Common Ancestor 2

In this article, we will explore one of the problems related to finding the ‘Lowest Common Ancestor (LCA)’ called ‘Finding the Lowest Common Ancestor 2’. This problem involves finding the lowest common ancestor of two nodes in a specific tree structure, particularly in a binary tree. The LCA problem is a fundamental problem associated with tree traversal and manipulation, frequently appearing in coding interviews and algorithm competitions.

Problem Description

Given a binary tree, we need to find the lowest common ancestor of two nodes u and v.
A binary tree can have a maximum of 2 children for each node, starting from the root node, and
each node has a unique value.

Input Format

First line: Number of nodes n (1 ≤ n ≤ 100,000)
Second line: Tree structure (given parent nodes and child nodes)
Third line: Two nodes u, v

Output Format

Output the lowest common ancestor of nodes u and v.

Example

Input:
7
1 2
1 3
2 4
2 5
3 6
3 7
4 5

Output:
2

Approach to the Problem

To solve this problem, we first need to construct the tree. The tree can be represented as an array or linked list, but
using a linked list is more efficient. Then, we will record the depth of each node through DFS (Depth First Search) and
store the parent nodes to easily find the LCA later.

Tree Construction

Based on the given edge information, we will establish the parent-child relationships for the nodes.
We will use Python’s dictionary to store the parent-child relationships.


from collections import defaultdict

def build_tree(edges):
    tree = defaultdict(list)
    for parent, child in edges:
        tree[parent].append(child)
    return tree

Storing Depth and Parent Node Information via DFS


def dfs(tree, node, parent, depth, depths, parents):
    depths[node] = depth
    parents[node] = parent
    for child in tree[node]:
        if child != parent:
            dfs(tree, child, node, depth + 1, depths, parents)

Implementing the LCA Function

After aligning the positions of the two nodes based on depth, we proceed upward along their parents until
both nodes converge at the same node.


def lca(u, v, depths, parents):
    # Aligning Depths
    if depths[u] < depths[v]:
        u, v = v, u

    while depths[u] > depths[v]:
        u = parents[u]

    while u != v:
        u = parents[u]
        v = parents[v]

    return u

Complete Code


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    u, v = map(int, input().split())

    tree = build_tree(edges)
    depths = {}
    parents = {}

    # Collecting depth and parent information via DFS
    dfs(tree, 1, -1, 0, depths, parents)

    # Finding the lowest common ancestor
    ancestor = lca(u, v, depths, parents)
    print(ancestor)

if __name__ == "__main__":
    main()

Time Complexity

The time complexity of the above algorithm is O(n). This is because each node is visited once during the tree construction and traversal.

Conclusion

The ‘Finding the Lowest Common Ancestor 2’ problem is helpful for understanding the basics of searching and manipulating binary trees,
and it is a practical algorithm. Through the process of solving this problem, one can gain a deep understanding of tree structures and the concept of DFS.
This algorithm can be extended to various other problems and is also very useful in the application of other data structures.