236-Lowest Common Ancestor Of a Binary Tree

So, the problem I chose for today is: Lowest Common Ancestor Of a Binary Tree

Before I start explaining the solution to this problem, I assume that the reader of this blog has a basic understanding of how Binary Search Trees (BST) work. If not, you can watch my YouTube video on the topic here:

Embedded content

Let's start:

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

According to the definition of LCA on Wikipedia: "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.

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.

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

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.

Solution:

The method first checks if the root is null or if either p or q is the same as the root. If any of these conditions are true, it means either p or q is the lowest common ancestor, so we return the root.
If none of the conditions are satisfied, we recursively call the lowestCommonAncestor method for the left and right children of the root.
It then checks the results from the left and right recursive calls:

If the result from the left subtree is null, it means both p and q are in the right subtree, so it returns the result obtained from the right subtree.
If the result from the right subtree is null, it means both p and q are in the left subtree, so it returns the result obtained from the left subtree.
If neither of the above conditions is true, it means p is in one subtree and q is in the other subtree, so the current root must be the lowest common ancestor. In that case, we return the root.

Basically, the code recursively checks the binary tree to find the lowest common ancestor of two given nodes p and q.

And you can find the GitHub gist here.

I hope I was able to explain the solution and it'll help and motivate you to start the challenge as well.

Leetcode challenge

Youtube

Instagram

References