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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohith Vazhathody

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.