Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@estring123]

you're assuming the tree is a binary search tree, what about binary trees that are not search trees? and what about non binary trees?

[@siddharthkapoor3867]

IDK WHY YOU STARTED THIS CHANNEL BUT THIS IS A BLESSING FOR people like me. THANK YOU SO MUCH !

[@leeroymlg4692]

He is single handedly starting thousands of careers

[@vladimirstrigunov7412]

You are one really rare talented teacher!

[@prafulparashar9849]

This code simplicity is God-level !! Dude, I went like, this is it?? Then, I realized that this was actually it.

[@plusorminus9177]

For real bro 🤯🤯

[@jaminchung341]

You have a talent for making me feel like I overcomplicate things. Thank you for this solution and all the videos you make, your talent at problem-solving and teaching is godly.

[@wtcxdm]

This is one of the questions that I stared for a long time but understood it immediately after half of the video. Thanks for the great explanation as always.

[@SiddharthChoudhary-rv9tt]

Same

[@michaelgranger3293]

For anyone like me confused by him comparing the values of the nodes, a bst is organized so that child nodes on the left are less than the parent node, and child nodes on the right are greater than the parent node. This applies recursively for any node with children.

[@unltdrider]

Was looking for this. Thanks!

[@SU-kx8mb]

Thank you! I was confused by that part.

[@romilrathi5940]

I have become substantial better in coding and solving difficult problems thanks to your channel. Keep it up!

[@nvssksuman9279]

Love from Suman(IIT-Bhubaneshwar, odisha India

[@harry5094]

My mind was blown after seeing your solution. Thanks my man!

[@HarimaKentaro]

ya, same here :P i was overthinking it and completely went over the fact that this was a BST even though it said so explicitly lool

[@kuoyulu6714]

After an hour, I finally did a O(n) solution, and i check NeetCode's video: 6 mins Me : ...

[@sandeepreddysomu2603]

Time Complexity will be O(n) in the worst possible case of tree being left skewed or right skewed. Anyway as always awesome explanation bro.

[@tomerva22]

I was also about to type that :)

[@Marcelo-yp9uz]

Still O(h)

[@studyaccount794]

But isn't that the same as O(h) where h is n?? So technically O(h) is the more correct solution because in the case you mentioned where it's O(n) it's also O(h).

[@XLpacman805]

But isn't a Binary Search Tree non-skewed unless stated?

[@stephennjuguna3793]

Wow! I had overcomplicated the solution for this. Thanks.

[@sumedha8206]

very elegant solution! i did not think of the concept that if both aren't greater or lesser, then we found the ancestor. mind blown when i saw that!

[@draugno7]

Recursive approach came out with a little bit better space complexity but both 100% regarding TC. Great approach!

[@FANSasFRIENDS]

After seeing your solution, it didn't took me a minute to solve this problem in c++, Really very nice, keep going.

[@shanshanyu5954]

Thanks!

[@NeetCode]

Hey Shanshan - thank you so much, I really appreciate it!! 😊

[@shanshanyu5954]

@@NeetCode Sorry, I only have a little money, I really appreciated your work but the amount can't represent my thanks. As a video maker, I know making video is a time consuming process. Your video helps me a lot. If I can find a full time job, I will donate more. Thanks for you sharing, your videos are better than many paid courses that I had before!

[@MIDNightPT4]

@@shanshanyu5954 Its the thought that counts!

[@asmahamdym]

It's amazing how simple and straightforward your solution is!

[@rileykirkham9690]

Dang that's such an easy solution. Here I was thinking I would find the paths to both p and q and see where the paths differed, but no. This is way better!

[@ms3801]

This question made my brain hurt a bit, so glad you were here to explain this for all of us! Just wanted to express my gratitude love the way you kind of do an overall explanation before you code.

[@chengjacky6460]

Amazing video, kindly remind this is for Leetcode 235 instead of 236. One is for binary tree (unsorted), the other is for binary search tree (sorted)

[@asdasdf3874]

Lmao I was on 236 thinking why nothing works

[@solodolo42]

Reminds me of the lowest common multiple (LCM) from math. You stop when a number cannot divide all the remainders at the same time. Thank you bro!

[@noelcovarrubias7490]

I came up with the "solution" where I was checking if the node's value was one of the 2 given nodes and if not, I would go either left or right until I would find the solution. Your explanation was so much better, and it makes total sense. I've been wanting to ask; how did you get good at this? Are there any books you would recommend?

[@marwaeltayeb]

You are one of the best people who can explain programming problems.

[@ethangordon3935]

Wow that was way easier than I was making it. I didn't think about A) doing it iteratively or B) simply returning root if you have to split directions like that. I guess I didn't fully understand the problem. Thank you!

[@hayatof1]

Hello. Loving all these videos and the neetcode website (even though I am learning very slowly). Just an update, this problem on Leetcode is being listed as a Medium now and not Easy anymore. Actually just saw the entire video and....what!? How did you....wow this one just blew my mind.

[@johnqu1t]

Man, your solutions always manage to impress me

[@BlanKaiX]

Reminder that this is the solution for 235 not 236 which has an unsorted binary tree

[@robinrpr]

This solution has totally threw me off after realizing that we can make use of the nature of a binary search tree. I need to take a closer look at binary trees structure next time

[@lingyundai964]

i honestly don't know what i would do without you, neetcode

[@shashankgowda9362]

for the test case 1,2,3 the code is not working

[@julieh_my]

Thank you so much! Please keep updating leetcode solutions! Your videos really help me a lot!! Great appreciate!

[@arthmodi9607]

coincidence! exactly after one year of upload seeing this video.! Big respect for you.!

[@danielsun716]

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': def dfs(root): if p.val < root.val and q.val < root.val: return dfs(root.left) if p.val > root.val and q.val > root.val: return dfs(root.right) return root return dfs(root)

[@innovatingforever2477]

this is what i was looking for thanks!!😁 I simplified it further def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if p.valroot.val: return self.lowestCommonAncestor(root.right,p,q) return root

[@quirkyquester]

Damn, I never knew this problem can be solved this way. Mind blown. Great approach. Thank you!

[@thepriestofvaranasi]

It is nowhere mentioned that the tree is a BST. So how did we conclude that a node with a value greater than the parent will always be in the right subtree and less than the parent will be in the left subtree?

[@rethern7966]

you are doing 236, this is 235

[@thepriestofvaranasi]

@@rethern7966 yeah I figured it out after sometime lol

[@parthnagdev]

@@rethern7966 you saved my life today, i owe you

[@davidshu9753]

recursive solution: 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) elif p.val > root.val and q.val > root.val: return self.lowestCommonAncestor(root.right, p, q) else: return root

[@julesrules1]

Thank you for the neat explanation. And the code as well.

[@deepaligarg7643]

Very neat solution and excellent explanation

[@unjinjang2234]

Amazing!! Thank you NeetCode

[@sailormetz7148]

Thanks for the explanation. However, I'm confused on how 6 isn't the LCA for 7 and 9 in the second example. I must be missing something in the definition of LCA, because 6 is lower than 8 and has both 7 and 9 as descendants...

[@leeroymlg4692]

it's not the 'lowest' value, but the lowest node on the tree. 8 is below 6 on the tree

[@ladydimitrescu1155]

@@leeroymlg4692 even i was confused thanks for the clarification !

[@samspeaks-hk1vp]

one test case fails for the solution provided in this video.

[@deliveringIdeas]

Here is the Java equivalent for those who are wondering: class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode current = root; while(true) { if(p.val > current.val && q.val > current.val) { current = current.right; } if(p.val < current.val && q.val < current.val) { current = current.left; } else { return current; } } } }

[@mohitchaturvedi4556]

Recursive solution: if (p.val = root.val) or ((p.val >= root.val and q.val

[@Tallonest]

Recursive solution is more inefficient, it has a call track overhead of O(n) worst case ina. Skewed tree and O(h = log n) best case

[@viceroyop6385]

Simple recursive method given the leetcode constraints, you could do this without declaring low/high/res but I include them for clarity low = min(p.val, q.val) high = max(p.val, q.val) res = root.val # LCA because going left subtree leaves out high, right subtree leaves out low if low = res: return root elif res > low and res > high: return self.lowestCommonAncestor(root.left, p, q) elif res < low and res < high: return self.lowestCommonAncestor(root.right, p, q)

[@davegeraghty2187]

is this still valid? the leetcode 236 example doesnt seem to structure the trees in the way you describe with right descendants being greater than the root

[@NewTypeVietnam]

it is a Binary Search Tree bro...

[@Jamal-code]

@NeetCode 4:59 I think the time complexity is O(n) because the BST isn’t necessarily balanced

[@sammyapsel1443]

Question: Assume the BST is example 1 and q=0,p=5. Can't I just write a helper function that returns the path to these values from the root ,in this case : q_path=[left,left] and p_path=[left,right,right] and then just check between the 2 paths what is the largest common prefix which will lead me from the root to the LCA, no? Wouldn't this work and also be O(logn) ?

[@tamchuminh7022]

I think a more intuitive solution is that you could record all the nodes when traversing from root to p in an array, and all the nodes to q in other array, then find the common node in these 2 arrays.

[@namoan1216]

Is it possible to solve this prob using recursion?

[@elgizabbasov1963]

if root.val < p.val and root.val < q.val: return self.lowestCommonAncestor(root.right, p, q) elif root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left, p, q) else: return root

[@tonianev]

@@elgizabbasov1963 Would this then be O(N) space because of the call stack?

[@hamoodhabibi7026]

@@tonianev yes worst case O(n) average O(log n)

[@whonayem01]

Thanks NeetCode! I think i wrote a little easier solution after watching your video explanation before watching coding part.

[@AnthonyInSanDiego]

Could you plz share that for a poor soul here

[@jointcc2]

there seem to be very little number of cases in the problem to realize, well done!

[@valentinfontanger4962]

Simple and effective solution !

[@QVL75]

Good explanation. Thanks.

[@art4eigen93]

Neet: "So I am gonna complete the solution in just 3 lines fellas"

[@Emorinken]

Thank you very much man

[@hidetominitta4149]

So is there some sort of official binary tree definition I can find? Isn't there a few presuppositions that are being made that make this problem easier? For one why does: TreeNode.left

[@tb0707-m8w]

this is binary SEARCH tree. Loot at the definition of that tree

[@mahesh_bvn]

Grateful to your work

[@jean4j_]

OMG! I'm so mad at myself I didn't see it. What a brilliant solution

[@Asdelatech]

Thank you so much dude!!!

[@samirpandit8899]

beautiful solution

[@mightyprogrammer2899]

Here is the code, u can run with your offline python environment class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class BinarySearchTreeNode: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': cur = root while cur: if p.val > cur.val and q.val > cur.val: cur = cur.right elif p.val < cur.val and q.val < cur.val: cur = cur.left else: return cur # Helper function to build a BST from a list def buildBST(nums): if not nums: return None root = TreeNode(nums[0]) for num in nums[1:]: if num is not None: root = insert(root, num) return root # Helper function to insert a value into a BST def insert(root, val): if not root: return TreeNode(val) if val < root.val: root.left = insert(root.left, val) else: root.right = insert(root.right, val) return root if __name__ == "__main__": solution = BinarySearchTreeNode() nums_1 = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5] p_val_1, q_val_1 = 2, 8 root1 = buildBST(nums_1) p1 = TreeNode(p_val_1) q1 = TreeNode(q_val_1) result1 = solution.lowestCommonAncestor(root1, p1, q1) print(result1.val) nums_2 = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5] p_val_2, q_val_2 = 2, 4 root2 = buildBST(nums_2) p2 = TreeNode(p_val_2) q2 = TreeNode(q_val_2) result2 = solution.lowestCommonAncestor(root2, p2, q2) print(result2.val) nums_3 = [2, 1] p_val_3, q_val_3 = 2, 1 root3 = buildBST(nums_3) p3 = TreeNode(p_val_3) q3 = TreeNode(q_val_3) result3 = solution.lowestCommonAncestor(root3, p3, q3) print(result3.val)

[@matthewbridges3147]

I made this massively more complicated for myself by ignoring the constraint that confirmed `p` and `q` will exist in the list. This becomes much more complicated if you're having to binary search for nodes, then traverse back up to find the first common ancestor of both.

[@radhikashroff2643]

Hi , looks like this solution is not getting accepted for me, curr = root while curr: if p.val > curr.val and q.val > curr.val: curr = curr.right elif p.val < curr.val and q.val < curr.val: curr = curr.left else: return curr Thanks

[@albertjtyeh53]

Hi @radhika i think you are looking at 235 not 236.

[@staazbeats]

Yeah it’s saying wrong answer for me too, but it passes the first test case

[@srinadhp]

same for me; does not pass in c++. First TC passes though. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode *cur = root; while (cur) { if (cur->left && p->val < root->val && q->val < root->val) { cur = cur->left; } else if (cur->right && p->val > root->val && q->val > root->val) { cur = cur->right; } else { return cur; } } return nullptr; }

[@dorondavid4698]

Works for me in C#

[@son0funiverse]

Yeah, it didn't work for me too.

[@hwang1607]

Wow great simple solution

[@NichoCode]

using recursion wouldnt the space complexity be O(logn) since the callstack will at most have logn recursive calls at a time?

[@SabinBajracharya]

This is not recursion, it's just a loop. You can also do while(true) { } and the solution will still work as we are guaranteed to find p and q

[@aaditya_87]

28/30 cases passed

[@sebastianduerr2952]

Really awesome, thank you!

[@ericliu2325]

Would the space complexity also be O( log n)?

[@dineshkumarkb1372]

Great video as always! Can you also solve lowest common ancestor of a binary tree please?

[@ben2258]

Anyone know why my solution to this problem might be passing on LeetCode but failing on NeetCode?

[@fanluo5010]

Really helpful! Thank you!

[@scotttang3646]

I tried just use root instead of cur, it still works.

[@jacksonqi4488]

can someone explain why the second if statement has to be an else if? i feel like, logically, it doesnt matter since we are going down the tree regardless. while root: if p.val < root.val and q.val < root.val: root = root.left if p.val > root.val and q.val > root.val: root = root.right else: return root

[@SabinBajracharya]

Yes it doesn't matter for the solution but regardless the compiler will evaluate the second "if" statement even if the first "if" statement is true. When we use "elseIf" the compiler will not evaluate any other condition if one of the condition is true

[@navaneethmkrishnan6374]

Hi. By this algorithm, wouldn't a case where p = 0 and q = 5 return an answer of 0. Shouldn't the answer be 2 as 0 is not an ancestor of 5?

[@ishank2160]

I think you are misunderstanding something here. When root is 2 (firstroot.left) then 0< 2 but 5>2 so root will be returned i.e. 2. I don't understand how you see 0 being returned.

[@vishalkumaar1]

What software or app do you use to get these videos done? Like is that apple pencil on ipad? @neetcode

[@ahmadzerie9088]

thanks for the explanation of the question but now this question its medium not easy

[@AzimBaghadiya]

you said that the space complexity is O(1) but shouldn't it be O(h) where h = height of the tree? Because we are using the call stack for the recursive calls.

[@The6thProgrammer]

There is no call stack in the solution given, there is a pointer to the current node being held which is constantly updated. This approach is iterative. For a recursive solution, you are correct.

[@The6thProgrammer]

To your point this could easily be done recursively which is what I did as well: class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val > root->val && q->val > root->val) { return lowestCommonAncestor(root->right, p, q); } else if (p->val < root->val && q->val < root->val) { return lowestCommonAncestor(root->left, p, q); } else { return root; } } };

[@symbol767]

Thanks man, liked

[@mastermax7777]

I didnt realize a binary search tree was sorted at first, and spent one hour trying to do bfs search lol

[@arunagiriswarane1155]

@neetcode can u discuss tower of hanoi problem. I think it helps us to set a base for recursive problem.

[@giantbush4258]

Wish you also solved the other (lowest common ancestor) binary tree problems. They are 4 of them.

[@adityamaskar2147]

Why I am getting wrong answer for this Input with code below: [3,5,1,6,2,0,8,null,null,7,4] 5 4 Output : null Expected : 5 ---------------------------------------- Code ---------------------------------------------------- class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': cur = root while cur: if p.val > cur.val and q.val > cur.val: cur = cur.right elif p.val < cur.val and q.val < cur.val: cur = cur.left else: return cur

[@ladydimitrescu1155]

God like explanation!

[@DaMavrk]

how is this medium but subtree of another tree easy? lol

[@asrahussain8642]

what if it's not a BST??

[@SarahSalvatore-ve6gf]

This no longer works for question 235

[@sucraloss]

Damnit I solved this using DP and felt good until I saw your insanely short and intuitive solution. I basically created a path to each node, popped values off the longer path and compared to the top of the shorter path until the path lengths were equal. When they were I popped off each value and compared and as soon as they were equal I returned the node where it was equal.

[@sanooosai]

thank you sir

[@patrickonielbernardo8786]

very clever

[@arnobchowdhury9641]

I solved the problem. But, overcomplicated it way too much. I found the 2 nodes separately first. And, then compared their traversal paths. The last matching node is the LCA.

[@mohamedantar1249]

i'm shocked by how your code is very simple while i wrote this much code: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode* head= root; //root equal to one of them if(root->val==p->val || root->val== q->val) return root; //p and q one at left and the other at right if(p->val < root->val && q->val > root->val || p->val > root->val && q->val < root->val) return root; //p,q both at right if(root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q); //p,q both at left if(root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q); return root; }

[@halahmilksheikh]

Should have mentioned straight away that p and q will exist and that p!=q like in the problem. Went too quickly over this one

[@srivatsansubramanian8535]

are binary trees always like this? such that values on the left are lower and right are higher?

[@wfkpk]

Yes your understanding is correct. root value will be greater than left and less than right.

[@matthewsaucedo2471]

@@wfkpk No, this is not correct. Binary SEARCH Trees are always like this. A plain old Binary Tree has no such guarantee.

[@matthewsaucedo2471]

And even then, you should always try and be clear if the BST allows duplicates and how that shakes out for the left/right sorting.

[@nirajankoirala6344]

LC problem number 235 and not 236!

[@zachcodes]

Is this still considered a DFS approach?

[@deepaligarg2978]

This solution is not working This is the below code I used following the video. But it does not pass all test cases. Please let me know if I missed something. var lowestCommonAncestor = function (root, p, q) { if (!root) return null; let curr = root; while (curr) { if (p.val < curr.val && q.val < curr.val) curr = curr.left; else if (p.val > curr.val && q.val > curr.val) curr = curr.right; else return curr; } };

[@zzhumash03]

Everything seems fine. I tried your exact code in leetcode, it passed

[@cici-lx6np]

I saw other comments say that this solution is for leetcode 235 instead of 236. The difference between 235 and 236 is that 235 is Binary Search Tree 236 is Binary Tree. Hope this could help :)

[@yashwanthsai762]

@@cici-lx6np tnx i was scratching my head

[@shubhaj2056]

and here i was writing 5 different functions for no reason

[@demaxl732]

I didnt even notice the fact that is was a BST and I solved it using recursion like a regular BT😂

[@nikhildinesan5259]

just a suggestion can you make video on task scheduler problem too ?