Solution in Java


  • 0
    N
    public class LCAinBinaryTree {
    
    	public static void main(String[] args) {
            Node root = new Node(1);
            root.left = new Node(2);
            root.right = new Node(3);
            root.left.left = new Node(4);
            root.left.right = new Node(5);
            root.right.left = new Node(6);
            root.right.right = new Node(7);
            
            Node lca=findLca(root, 3, 5);
            if(lca==null)
            	System.out.println("Keys not present");
            else
            	System.out.println(lca.val);
    	}
    
    	static Node findLca(Node root, int n1, int n2) {
    		Found f1 = new Found(false);
    		Found f2 = new Found(false);
    		Node lca = findLcaUtil(root, n1, n2, f1, f2);
    		if (f1.isFound && f2.isFound || f1.isFound && find(lca, n2) || f2.isFound && find(lca, n1))
    			return lca;
    		else
    			return null;
    	}
    
    	private static Node findLcaUtil(Node node, int n1, int n2, Found f1, Found f2) {
    		if (node == null)
    			return null;
    
    		if (node.val == n1) {
    			f1.isFound = true;
    			return node;
    		}
    		if (node.val == n2) {
    			f2.isFound = true;
    			return node;
    		}
    
    		Node leftLca = findLcaUtil(node.left, n1, n2, f1, f2);
    		Node rightLca = findLcaUtil(node.right, n1, n2, f1, f2);
    		if (leftLca != null && rightLca != null) {
    			return node;
    		}
    
    		return (leftLca != null) ? leftLca : rightLca;
    	}
    
    	private static boolean find(Node lca, int n) {
    		if (lca == null)
    			return false;
    		if (lca.val == n)
    			return true;
    		return find(lca.left, n) || find(lca.right, n);
    	}
    
    	private static class Found {
    		boolean isFound;
    
    		Found(boolean isFound) {
    			this.isFound = isFound;
    		}
    	}
    
    	private static class Node {
    		int val;
    		Node left;
    		Node right;
    
    		Node(int val) {
    			this.val = val;
    		}
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.