Prerequisites :- Binary Trees, LCA.
Problem :- Given a binary tree and three nodes A, B and C. Find the lowest common ancestor of the three nodes.
Note:
- A binary tree is a tree data structure in which every node has at most 2 children nodes.
- Lowest common ancestor of node A, B and C is defined as the lowest node in the tree such that subtree rooted at that node contains all the nodes A,B and C.
- A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.
Solution Approach: The provided solution employs a recursive approach to find the LCA of a pair of nodes and then uses this result to find the LCA with the third node. The key function here is findLCA(), which recursively searches for the LCA of a set of nodes in the binary tree.
Let’s break-down the findLCA() function:
- The function takes the root of the binary tree and a set of nodes.
- It checks if the current node’s data is in the set. If yes, it returns the current node.
- It then recursively searches for the LCA in the left and right subtrees.
- If both left and right LCA are found, it means the current root is the LCA.
- It returns the non-null LCA (either left or right).
Time Complexity :- The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. Each node is visited once during the traversal.
Space Complexity :- The space complexity is O(H), where H is the height of the binary tree. This space is used for the recursive call stack during the traversal. The additional space for the unordered set is O(1) since it has a constant number of elements (three nodes).