LCAN3 - Editorial

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.


  • 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).