Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

121. Lowest Common Ancestor of a Binary Tree

MediumDay 36 of 60Trees & BST

Given the root of a binary tree and two nodes p and q that are both in the tree, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as an ancestor of itself. All values are unique. (In the tests, p and q are given by value and the judge passes the matching nodes.)

Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
5 is an ancestor of 4, and a node is an ancestor of itself.
Constraints
  • The number of nodes is in the range 2 to 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique, p != q, and both exist in the tree
Hints
Frequently asked at: Meta, Amazon, Microsoft, LinkedIn, Google
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min