Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given the root node of a binary tree. Return a list consisting of each level of the tree (we will have a list of lists, a list for each level's items), where each level is traversed from left to right. A level order traversal.
What Do We Know?
We know our preorder, inorder, and postorder traversals...but this is a little different.
We want to go level by level here...what does this remind us of?
Every acyclic connected graph is a tree, and all trees are acyclic connected graphs.
This unlocks our ability to search a tree list we search a graph, using Breadth First Search and Depth First Search.
DFS will go deep, and BFS will go out level by level. We want BFS since it is a more natural approach to something like this.
We realize that this is just the breadth-first search of a tree structure.
We shift our knowledge from graph search to this problem.
Complexities
n is the total amount of nodes in the binary tree
Time: O( n )
Space:
With output: O( n ) because we will store n nodes in the list of levels structure.
Without output: O( n ) the queue at maximum at any point in time will hold some fractional component of the total nodes in the tree.
The fractional constant disappears and the asymptotic behavior is linear.
We can't bound the max space in the queue to the widest level because when we process the widest level...if there is a level below it we will have all the nodes from the widest level PLUS what we are adding into the queue as we process each node in the level (we remove 1 node and can add 2 children which will push us past the size of the widest level initially).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
4 окт 2024
