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.orgBecome a member:
https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/joinDonation (appears on streams):
https://streamlabs.com/easytheory1/tipPaypal:
https://paypal.me/easytheoryPatreon:
https://www.patreon.com/easytheoryDiscord:
https://discord.gg/SD4U3hsMerch:
Language Hierarchy Apparel:
https://teespring.com/language-hierarchy?pid=2&cid=2122Pumping Lemma Apparel:
https://teespring.com/pumping-lemma-for-regular-langIf 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