LeetCode 235. Lowest Common Ancestor of a Binary Search Tree (Algorithm Explained)

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@jaspreets1097]

Hey! There is another problem on leetcode which is literally the same exact thing but not a 'binary SEARCH tree', its considered Medium difficulty and I came up with a really inefficient solution haha. Would love to see you explain that since the tree nodes are not sorted. I find your videos really helpful bro, especially this time of year. Keep it up, looking forward to great content!

[@Turnpost2552]

Be more with specific the names.

[@jodog31]

I know what you mean, I actually got the two confused initially. It's 236. Lowest Common Ancestor of a Binary Tree. I would like to know how he did that one too.

[@ziqixu5380]

That's awesome! Watching your videos has become my new daily routine.

[@hassansmallah]

wow! that's easy! Thank you
Python:
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root

[@nagarjunareddypadala1585]

Your explanation and problem solving is great. I would also like to know the time complexity and space complexity with explanation as these will be expected by any interviewer. :)

[@somyasrivastava6315]

This is so beautiful Nick..Thanks for the explanation.

[@rishabhjain4546]

You treat problems as if they are nothing. I like that attitude so much. Makes any problem easier.

[@pealhasan]

bro everytime you explain a solution it sounds so easy 😭GOAT

[@1levente371]

i think there is a problem, if p and q is 0,and 5 in the first example then it would just return the root?which is not correct

[@anmolbindroo7354]

What will happen in the case of two nodes directly connected to each other?

[@guambomber448]

It will return the parent of the two nodes connected to each other because both if statements will return false

[@dishagupta7446]

What will ne time complexity

[@tijilparmar5758]

Love the explanations!

[@dunkyzhang2067]

runtime error: member access within null pointer of type 'TreeNode'

[@ok123ut]

yeah i was waiting on him to click on submit..

[@shraddhashetty8659]

I got the same error but that was because i was missing return keyword within the if condition.
if(p.valroot.val) {
*return* lowestCommonAncestor(root.right,p,q);
}
works fine for me

[@ok123ut]

@@shraddhashetty8659 interesting i still see that error even with the returns.

[@AnandBaburajan]

Maybe you are looking for the solution to 'binary tree' and not 'binary search tree'

[@prakashreddy5549]

@@AnandBaburajan Thanks man! I was new to coding and literally executed this same code (binary search tree) in binary tree question on leetcode. 😄

[@dimas-]

This is brilliant

[@shivanshnegi6957]

keep up the good work brother

[@chrisyang05]

This solution assumes the nodes being searched exist somewhere in the tree i.e. no invalid input.

[@AbhishekSharma-kc7ic]

where is base case if root is null and why its not there?

[@adityabadhe3295]

no base case required as he is returning the root anyway.

[@GauravSingh-ku5xy]

Thanks buddy.

[@sharmadenesh]

This will throw null pointer exception if root itself is null

[@harenderbhardwaj6357]

some test cases are failing on leetcode for this solution

[@1levente371]

yes if p and q is 0 and 5 in the first example and it would be wrong

[@JohnWick-kh7ow]

It's giving me runtime error.

[@ScaerCroe]

Nice shirt!

[@user-df8eq7hu9b]

good

[@marcoflores1764]

Nice

[@biswamohandwari6460]

Man damn you are a super genius 👌

[@ahmedfattah5879]

6

[@prashantsah5901]

This solution only works for the Binary Search Tree (BST) and not for the General Binary Tree.

[@Vishal-joshi1998]

wow

[@AniketSomwanshi-ll7mz]

Correction in the code :
if(p->val == root->val || q->val == root->val)
return root;
This will be the first thing to check. Thanks for the solution @Nick White

[@dhanushkumar9639]

error -->runtime error: member access within null pointer of type 'TreeNode' (solution.cpp)

[@AniketSomwanshi-ll7mz]

@@dhanushkumar9639 check if root itself is null

[@Viz4rd]

I just feel dumb now:)

[@rojka-_-]

same