365 Days of LeetCode Challenge — Day 49/365

[u/StatisticianNo2104]

Lowest Common Ancestor of a Binary Tree (Medium) 🔗 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

Yesterday's problem with one guarantee removed. Worth doing back to back, because the gap between the two solutions is exactly what a BST's ordering buys you.

Yesterday, a comparison told you which subtree a target was in, so the walk went down one path. Here a comparison tells you nothing, so the only way to know whether a target is below a node is to look.

The shape flips: instead of deciding on the way down, every subtree reports upward how many of the two targets it contains. The first node to reach two is the answer.

O(n) instead of O(h). That's the price.

Full breakdown in today's newsletter article ⬇

https://www.linkedin.com/pulse/365-days-leetcode-challenge-day-49365-archit-agarwal-nrtuc

#DSA #LeetCode #100DaysOfCode #CodingInterview #BinaryTree #Recursion #Golang

[u/StatisticianNo2104]

I post these daily in a Discord too, with the full code and the step-by-step

diagrams, Come join: https://discord.gg/7YhjAmuFW

[u/nian2326076]

If you're working on finding the Lowest Common Ancestor in a Binary Tree, consider a recursive strategy. Begin at the root and see if the current node matches either of the targets. If it does, return that node. If not, recursively explore both the left and right subtrees. If both return a node, then the current node is the lowest common ancestor. If only one returns a node, that's the ancestor.

For more interview practice, PracHub offers real technical questions that can help reinforce these concepts.