Binary Tree Level Order Traversal II
Performing a bottom-up level order traversal of a binary tree requires a slight modification to the standard level order traversal. Here are the steps to perform the traversal:
- Use a Queue: Utilize a queue to iterate through the nodes level by level, as in a standard level order traversal.
- Store Each Level: Store the values of nodes at each level in a separate list.
- Reverse the Order: After storing the values of all levels, reverse the order of the lists to get the bottom-up level order.
Here’s code to achieve the task:
|
|
Key Insights:
- The
deque
from thecollections
module is used for efficient pop operations from the front of the queue. - Each iteration through the while loop processes one level of the tree, adding child nodes to the queue.
- The result list is reversed to provide the bottom-up level order.
This algorithm runs in ( O(n) ) time complexity, where ( n ) is the number of nodes in the tree, and uses ( O(n) ) space.
Define the Terms Binary Tree: A tree with 0 to 2 children. Leaf node has 0 children. Intermediate nodes can have 1 or 2 children. Root can also have 1 or two children. Bottom up level: Go from the bottom of the tree and traverse all the nodes at the last level first. Then keep going towards the root. We will grab all the node values at the same level and add it to the output.
Define the Interface Input: root (of the binary tree) Output: array of arrays (integers)
Analyze the Input and Output Edge case: root is null, return empty array Corner case: only the root is given, return the value of the root in the array : [[1]] (example 2)
Identify the Invariants
- You can visit a node only once
- You cannot mix the nodes at different levels.
Identify the constraints
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
Search the Problem Space
Classify the Problem Binary Tree Level Order Traversal
Usual traversal is from left to right, top to bottom. In this case, bottom to top and left to right.
Analyze the Examples
Solve the Problem by Hand We are given the reference to the root of the binary tree Same thing as the problem Binary Tree Level Order Traversal and reverse the output
102: [[3],[9,20],[15,7]] 107: [[15,7],[9,20],[3]]
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Analyze Time and Space Complexity
Time: O(N) or O(2^L) Space: O(N)
Outline the Solution
- Level order traversal
- Reverse the output and return
Key Takeaways
[] [[]]
[[3]] [[3], []]
[[3], [9, 20]]
|
|
Define the Terms Binary Tree: A tree with 0 to 2 children. Leaf node has 0 children. Intermediate nodes can have 1 or 2 children. Root can also have 1 or two children. Bottom up level: Go from the bottom of the tree and traverse all the nodes at the last level first. Then keep going towards the root. We will grab all the node values at the same level and add it to the output.
Define the Interface Input: root (of the binary tree) Output: array of arrays (integers)
Analyze the Input and Output Edge case: root is null, return empty array Corner case: only the root is given, return the value of the root in the array : [[1]] (example 2)
Identify the Invariants
- You can visit a node only once
- You cannot mix the nodes at different levels.
Identify the constraints
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
Search the Problem Space
Classify the Problem Binary Tree Level Order Traversal
Usual traversal is from left to right, top to bottom. In this case, bottom to top and left to right.
Analyze the Examples
Solve the Problem by Hand We are given the reference to the root of the binary tree Same thing as the problem Binary Tree Level Order Traversal and reverse the output
102: [[3],[9,20],[15,7]] 107: [[15,7],[9,20],[3]]
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Analyze Time and Space Complexity
Time: O(N) or O(2^L) Space: O(N)
Outline the Solution
- Level order traversal
- Reverse the output and return
Key Takeaways
[] [[]]
[[3]] [[3], []]
[[3], [9, 20]]
def wrapper(node, level, output) if output.size == level output « [] end
Unit of work
output[level] << node.val
Left child
if node.left
wrapper(node.left, level+1, output)
end
right child
if node.right
wrapper(node.right, level+1, output)
end
end
def level_order_bottom(root) if root.nil? return [] end output = [] wrapper(root, 0, output) output.reverse end
|
|
Define the Terms Binary Tree: A tree with 0 to 2 children. Leaf node has 0 children. Intermediate nodes can have 1 or 2 children. Root can also have 1 or two children. Bottom up level: Go from the bottom of the tree and traverse all the nodes at the last level first. Then keep going towards the root. We will grab all the node values at the same level and add it to the output.
Define the Interface Input: root (of the binary tree) Output: array of arrays (integers)
Analyze the Input and Output Edge case: root is null, return empty array Corner case: only the root is given, return the value of the root in the array : [[1]] (example 2)
Identify the Invariants
- You can visit a node only once
- You cannot mix the nodes at different levels.
Identify the constraints
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
Search the Problem Space
Classify the Problem Binary Tree Level Order Traversal
Usual traversal is from left to right, top to bottom. In this case, bottom to top and left to right.
Analyze the Examples
Solve the Problem by Hand We are given the reference to the root of the binary tree Same thing as the problem Binary Tree Level Order Traversal and reverse the output
102: [[3],[9,20],[15,7]] 107: [[15,7],[9,20],[3]]
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Analyze Time and Space Complexity
Time: O(N) or O(2^L) Space: O(N)
Outline the Solution
- Level order traversal
- Reverse the output and return
Key Takeaways
[] [[]]
[[3]] [[3], []]
[[3], [9, 20]]
|
|
|
|
|
|