Lowest Common Ancestor in Binary Tree Editorial

Practice Problems Link: Lowest Common Ancestor in Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

The lowest common ancestor of two nodes p and q is the lowest node in the binary tree that has p and q as its descendants.
Note: A node is also considered a descendant of itself.

Given the reference to the root node and two nodes p and q in a binary tree, return the reference to the lowest common ancestor of p and q.

Note: You can assume that p and q will be present in the tree.

Approach

The idea is to traverse the given tree recursively and for each node, there will be three possibilities.

1. If the current node is equal to any of the given node then the current node will be the LCA.
2. Otherwise, recursively check the left and right subtree for LCA. If one of the subtrees has both p and q then it will also have the LCA.
3. Otherwise, if each subtree has one of the given nodes then the current node will be the LCA.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
    if (root == NULL) {
		return NULL;
	}
	if (root == p || root == q) {
		return root;
	}
	Node* leftSubtree = lowestCommonAncestor(root->left, p, q);
	Node* rightSubtree = lowestCommonAncestor(root->right, p, q);
	if (leftSubtree == NULL) {
		return rightSubtree;
	}
	if (rightSubtree == NULL) {
		return leftSubtree;
	}
	return root;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	
	Node lowestCommonAncestor(Node root, Node p, Node q) {
	    if (root == null) {
			return null;
		}
		if (root == p || root == q) {
			return root;
		}
		Node leftSubtree = lowestCommonAncestor(root.left, p, q);
		Node rightSubtree = lowestCommonAncestor(root.right, p, q);
		if (leftSubtree == null) {
			return rightSubtree;
		}
		if (rightSubtree == null) {
			return leftSubtree;
		}
		return root;
	}
}