Google Coding Interview Question: Deepest Node in a Binary Tree - Easy Theory

Here we give two algorithms to find the "deepest" node in a binary tree, one that is recursive and one that is iterative and based on breadth-first search. Both of them run in linear time in the size of the input tree. In the recursive one, we separate out the possible cases of the tree: either it is empty, has exactly one node, or otherwise. We then combine the recursive solutions and add 1 to the depth of whatever the deepest node was on that side. For the iterative one, we use breadth-first search, but "stop" the algorithm at the very end, and keep the last node that was enqueued, since BFS traverses the tree in "level order," so the last node added must be at the deepest level.

Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su

Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs

Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com

▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=vV10FTdXnLg