Lowest Common Ancestor (LCA)
Hard Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Find the Lowest Common Ancestor (LCA) of two nodes in a binary tree., Binary Tree, Tree Traversal, Recursion, Depth-First Search, Time Complexity, Space Complexity, Node, tree algorithms, divide and conquer, binary tree, recursion, time complexity analysis, tree traversal, Lowest Common Ancestor (LCA).
Given a binary tree, find the Lowest Common Ancestor (LCA) for two given nodes, x and y. The Lowest Common Ancestor (LCA) of two nodes x and y is defined as the lowest node in the tree that has both x and y as descendants (where a node is allowed to be a descendant of itself). Example Tree Structure for Reference: 1 / \ 2 3 / \ / \ 4 5 6 7 Example 1: Input: x = 4, y = 5 Output: 2 Explanation: All common ancestors for nodes 4 and 5 are 2 and 1. The lowest common ancestor among them is 2. Example 2: Input: x = 2, y = 3 Output: 1 Explanation: The lowest common ancestor for nodes 2 and 3 is 1. Example 3: Input: x = 6, y = 7 Output: 3 Explanation: The lowest common ancestor for nodes 6 and 7 is 3.