Linked List in Binary Tree (BFS + DFS + Preorder Traversal)

Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: https://algoswithmichael.com

🎧 Join the community Discord:   / discord  
💰 Support me on Patreon:   / michaelmuinos  
🔗Follow me on LinkedIn:   / michael-muinos  
📂Follow me on Github: https://github.com/MichaelMuinos

In this video, I go over the LeetCode problem "Linked List in Binary Tree". We are given a binary tree and linked list and must determine if the linked list is found in a downward direction inside of the binary tree. This problem can be solved in a couple different ways including depth-first search, breadth-first search, preorder traversal, and dynamic programming. Using a depth-first search is critical because we need to check to see if the head of our linked list is anywhere in our tree, if it is, we can choose to use a breadth-first search or a depth-first search to search for the rest of the nodes.

In each recursive call, we return true or false where the value determines if we have found our path or not. If we return true from our root recursive call, that means we successfully found the linked list somewhere in our binary tree. The time complexity of the solutions are O(N * min(L, H)) where N is the number of nodes we have in our tree, L is the length of our linked list, and H is the depth of the tree. The space complexity is going to be O(H) where H is the depth of our tree as well.