236-Lowest Common Ancestor Of a Binary Tree
Leetcode 75-day challenge
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:
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.
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
andq
will exist in the tree.
Solution:
- The method first checks if the root is null or if either
p
orq
is the same as the root. If any of these conditions are true, it means eitherp
orq
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
andq
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
andq
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 andq
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.
References