Leetcode 236. Lowest Common Ancestor of a Binary Tree

Accepted Code

Problem Statement

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).”

Test Cases

Example 1:

Taken from Leetcode.com

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:

Taken from Leetcode.com

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].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Approach

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.

So we mainly need to check for some cases.

1. Whether our node is already null, if yes then return null.
2. Whether our node is equal to p or q. The root will surely be the LCA for p and q. Return node in this case.
3. Take the left subtree and right subtree in a recursive way.
   left = fun(node.left, p, q) and right = fun(node.right, p, q).
4. If both left and right are null, we return null.
5. If both left and right are not null, we return the node as the root note will be the LCA here.
6. Otherwise, we check whether left != null, then return left or right != null, then return right.

Time and Space Complexity

We are traversing the whole tree in the worst case. So if the total number of nodes = n, then time complexity will be O(n) where n = number of nodes.

Space complexity will be O(H) where H = height of the tree.

Code

Java Code

LeetCodeTopInterviewQuestions/26_Lowest_Common_Ancestor_Of_A_Binary_Tree.java at master ·…