Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

1. Its a binary tree (a tree having atmost 2 children)
2. A node can be descendant of itself so the node is included to be an ancestor node, example b/w nodes of differet levels the higher level node can be common for both nodes
3. We need to keep track of the parent of each node as we move in the tree
4. For simplicity we choose stack as we need to move left and right both at the same time
5. move in left subtree first and then in right subtree
6. pick a map and keep adding current node parent to it(only till we find the target nodes while traversal)
7. keep a set and add target1 path to it
8. check which first node from path traversal of target2 is included in node1 path

private Node lowestCommonAncestorInATree(Node root, Node target1, Node target2) {
        
    //we need to keep storing all the ancestors for the node somewhere
    //how we should decide which one is lower (map raversal would tell this) ? and each node is the descendant of itself
    //how to find common descendant of both given nodes? (set would tell it)
    //think about corner cases, both nodes should be given , if one of them is root answer is root
    //why we need stack ???? because to move in the nodes, we can use recursion also

    Stack<Node> stack = new Stack<>();
    map.put(root, null);

    //map stores parent of each node
    while (!map.containsKey(target1) || !map.containsKey(target2)) {
        
        Node node = stack.pop();
         if(node.left != null) {
            map.put(node.left, node);
            stack.push(node.left);
         }

         if(node.right != null) {
            map.put(node.right, node);
            stack.push(node.right);
         }
     }
     HashSet<Node> set = new HashSet<>();
      
     //target will be null when we will reach the parent/root node
     while (target1 != null) {
        set.add(target1);
        target1 = map.get(target1); //here the parent keep changing
     }

     while (!set.contains(target2)) {
        //no need to add the data to the set now
        target2 = map.get(target2);
     }
     return target2;
   }