Lowest Common Ancestor of 2 nodes in a Binary Tree

Algorithm/Insights

1. Traverse the tree in bottom up approach.
2. If a node ( A or B ) is found, return it to its parent.
3. Parent will check if it was able to get nodes from both of its child.
4. If yes, then Parent is LCA.
5. If no, Parent will return NULL if none of its child returned A or B ELSE will return not NULL node.

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());
	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)