\n 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.\n<\/p>\n
\n Given a binary tree, we need to find the lowest common ancestor of two nodes \n Output the lowest common ancestor of nodes \n To solve this problem, we first need to construct the tree. The tree can be represented as an array or linked list, but \n Based on the given edge information, we will establish the parent-child relationships for the nodes. \n After aligning the positions of the two nodes based on depth, we proceed upward along their parents until \n The time complexity of the above algorithm is O(n). This is because each node is visited once during the tree construction and traversal.\n<\/p>\n \n The ‘Finding the Lowest Common Ancestor 2’ problem is helpful for understanding the basics of searching and manipulating binary trees, <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"u<\/code> and v<\/code>.
\n A binary tree can have a maximum of 2 children for each node, starting from the root node, and
\n each node has a unique value.\n<\/p>\nInput Format<\/h3>\n
\n
n<\/code> (1 \u2264 n \u2264 100,000)<\/li>\nu<\/code>, v<\/code><\/li>\n<\/ul>\nOutput Format<\/h3>\n
u<\/code> and v<\/code>.\n<\/p>\nExample<\/h2>\n
\nInput:\n7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 5\n\nOutput:\n2\n<\/pre>\n
Approach to the Problem<\/h2>\n
\n using a linked list is more efficient. Then, we will record the depth of each node through DFS (Depth First Search) and
\n store the parent nodes to easily find the LCA later.\n<\/p>\nTree Construction<\/h2>\n
\n We will use Python’s dictionary to store the parent-child relationships.\n<\/p>\n\nfrom collections import defaultdict\n\ndef build_tree(edges):\n tree = defaultdict(list)\n for parent, child in edges:\n tree[parent].append(child)\n return tree\n<\/code><\/pre>\nStoring Depth and Parent Node Information via DFS<\/h2>\n
\ndef dfs(tree, node, parent, depth, depths, parents):\n depths[node] = depth\n parents[node] = parent\n for child in tree[node]:\n if child != parent:\n dfs(tree, child, node, depth + 1, depths, parents)\n<\/code><\/pre>\nImplementing the LCA Function<\/h2>\n
\n both nodes converge at the same node.\n<\/p>\n\ndef lca(u, v, depths, parents):\n # Aligning Depths\n if depths[u] < depths[v]:\n u, v = v, u\n\n while depths[u] > depths[v]:\n u = parents[u]\n\n while u != v:\n u = parents[u]\n v = parents[v]\n\n return u\n<\/code><\/pre>\nComplete Code<\/h2>\n
\ndef main():\n n = int(input())\n edges = [tuple(map(int, input().split())) for _ in range(n - 1)]\n u, v = map(int, input().split())\n\n tree = build_tree(edges)\n depths = {}\n parents = {}\n\n # Collecting depth and parent information via DFS\n dfs(tree, 1, -1, 0, depths, parents)\n\n # Finding the lowest common ancestor\n ancestor = lca(u, v, depths, parents)\n print(ancestor)\n\nif __name__ == \"__main__\":\n main()\n<\/code><\/pre>\nTime Complexity<\/h2>\n
Conclusion<\/h2>\n
\n 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.
\n This algorithm can be extended to various other problems and is also very useful in the application of other data structures.\n<\/p>\n