Code Snippet
package com.ideserve.saurabh.questions;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* <br><br>
* Lowest Common Ancestor of 2 nodes in a Binary Tree</b><br>
* Given a binary tree and 2 tree nodes A and B, find the lowest common ancestor of the nodes.
* <br><br>
* <a href="https://www.youtube.com/watch?v=NBcqBddFbZw">Lowest Common Ancestor Youtube Link</a>
* @author Saurabh
*
*/
public class LowestCommonAncestor {
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public TreeNode getLowestCommonAncestor(TreeNode A, TreeNode B) {
return getLowestCommonAncestor(root, A, B);
}
private TreeNode getLowestCommonAncestor(TreeNode curr, TreeNode A, TreeNode B) {
if(curr == null) {
return null;
}
// If we find p or q, we return the node
if(curr == A || curr == B)
return curr;
// Recursive calls to find LCA in left and right subtrees
TreeNode leftNode = getLowestCommonAncestor(curr.getLeft(), A, B);
TreeNode rightNode = getLowestCommonAncestor(curr.getRight(), A, B);
// If we found p and q in left or right subtree of the current node,
// this means current node is a common ancestor, so return the node
if(leftNode != null && rightNode != null)
return curr;
// If we found p or q in left or right subtree of the current node,
// the means current node is an ancestor, return the node
if(leftNode == null) {
return rightNode;
} else {
return leftNode;
}
}
/**
* Defines a tree node
* @author Saurabh
*
*/
class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data, TreeNode left, TreeNode right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public TreeNode() {
super();
}
public TreeNode(int data) {
super();
this.data = data;
}
@Override
public String toString() {
return data+"";
}
}
/*
* *******************************************
* Methods for testing getLowestCommonAncestor
* *******************************************
*/
public static void main(String[] args) {
LowestCommonAncestor tree = new LowestCommonAncestor();
tree.createSampleTree();
TreeNode A = tree.getRoot().getLeft().getLeft(); // Node 4
TreeNode B = tree.getRoot().getRight(); // Node 3
TreeNode lca = tree.getLowestCommonAncestor(A, B);
System.out.println("LCA of " + A.getData() + " and " + B.getData() + " is " + lca);
}
/*
* Create a sample tree
* 1
* 2 3
* 4 5 6 7
*
*/
public void createSampleTree() {
root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
}
/*
* Print inorder traversal
*/
public void printInorder() {
printInorder(root);
}
private void printInorder(TreeNode root) {
if(root == null) {
return;
}
printInorder(root.getLeft());
System.out.print(root.getData() + " ");
printInorder(root.getRight());
}
}