Find Lowest Common Ancestor for Binary Tree with 2 Nodes as Input
class Solution {
//Handling if isFirstNodeFound and isSecondNodeFound is found to avoid //stack recursion processing unnecessarily if LCA is found.
static boolean isFirstNodeFound = false;
static boolean isSecondNodeFound = false;
public static Node lca(Node root, Node node1, Node node2) {
if(root == null) return null;
//Handling if any of target node is null , then other node itself will be treated //as LCA
if(node1==null)return node2;
if(node2 == null) return node1;
isFirstNodeFound = true;
return root;
}
if(root.val == node2.val){
isSecondNodeFound = true;
return root;
}
Node left = lca(root.left, node1, node2);
if(isFirstNodeFound && isSecondNodeFound){
//Here by using boolean variables , we are avoiding unnecessarily stack calls //if LCA is found already
if(isFirstNodeFound && isSecondNodeFound){
}
Node right = lca(root.right, node1 , node2);
if(left != null && right!= null){
return root;
}
if(left != null) return left;
if(right!=null) return right;
return null;
}
}
