Binary Tree Common Ancestor Problem Leetcode (Find common ancestor of nodes in binary tree)

Problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the Wikipedia, LCA is defined as:: “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).”

 Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the tree

This problem is popular in LeetCode and GeeksForGeeks. A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution:

	/**
	find common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not
	necessarily a binary search tree.
	*/
	/**
	Method1:
	-first we find on which side of the root node, the two nodes are located
	-if both the nodes are on different side of a root node, the root node will be the common ancestor
	-if the nodes are on same side, then we recursively check to find the node that splits the node into different subtree
	*/
	public class BinaryTreeCommonAncestor{
	/**
	check if the root node covers the node
	*/
	public static boolean nodeCovers(TreeNode root, TreeNode node){
	if(root == null){
	return false;
	}
	if(root==node){
	return true;
	}
	return nodeCovers(root.left, node) || nodeCovers(root.right, node);
	}
	/**
	find the common ancestor of node1 and node2 in the tree with root node at root
	*/
	public static TreeNode findCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2){
	if(root ==null){
	return null;
	}
	if(root==node1 || root==node2)
	return root;
	//first check if the nodes are present in the tree, if not return null
	if(!nodeCovers(root, node1) || !nodeCovers(root, node2)){
	return null;
	}
	//check if node1 is covered by left
	boolean isLeft1 = nodeCovers(root.left, node1);
	//check if node2 is covered by left
	boolean isLeft2 = nodeCovers(root.left, node2);
	if(isLeft1!=isLeft2){//both are on different side
	return root;
	}else{
	if(isLeft1==isLeft2){//both are on left side
	return findCommonAncestor(root.left, node1, node2);
	}else{//both are on right side
	return findCommonAncestor(root.right, node1, node2);
	}
	}
	}
	public static void main(String args[]){
	//create a tree
	TreeNode root = new TreeNode(0);
	TreeNode one = new TreeNode(1);
	TreeNode two = new TreeNode(2);
	TreeNode three = new TreeNode(3);
	TreeNode four = new TreeNode(4);
	TreeNode five = new TreeNode(5);
	root.left = one;
	root.right = two;
	one.parent = root;
	two.parent = root;
	one.left = three;
	one.right = four;
	three.parent = one;
	four.parent = one;
	three.left = five;
	five.parent = three;
	TreeNode node1 = three;
	TreeNode node2 = five;
	TreeNode anc = findCommonAncestor(root, node1, node2);
	System.out.println("common ancestor of "+node1.val+" and "+node2.val+" is "+(anc==null?"NONE":anc.val));
	}
	}

view raw BinaryTreeCommonAncestor.java hosted with ❤ by GitHub