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:

1. Use a Queue: Utilize a queue to iterate through the nodes level by level, as in a standard level order traversal.
2. Store Each Level: Store the values of nodes at each level in a separate list.
3. 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from collections import deque

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = deque([root])
        result = []

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result[::-1]  # Reverse the order of the levels

Key Insights:

• The deque from the collections 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]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[][]}
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]]

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[][]}
def level_order_bottom(root)
  output = []
    if root.nil?
        return []
    end
    level = 0
    queue = [root]

    while !queue.empty?
       size = queue.size
        output[level] = []

        size.times do
           node = queue.shift
            output[level] << node.val
            if node.left
                queue << node.left
            end
            if node.right
                queue << node.right
            end
        end

        level += 1
    end

    return 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]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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


def level_order_bottom(root)
  output = []
    if root.nil?
        return []
    end
    level = 0
    queue = [root]

    while !queue.empty?
       size = queue.size
        output[level] = []

        size.times do
           node = queue.shift
            output[level] << node.val
            if node.left
                queue << node.left
            end
            if node.right
                queue << node.right
            end
        end

        level += 1
    end

    return output.reverse
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int findMaxLen(TreeNode* root)
{
    if(root==NULL) return 0;
    return 1+max(findMaxLen(root->left),findMaxLen(root->right));
}
void levelOrderRec(TreeNode* root, vector<vector<int>>& vec, int level)
{
    if(root==NULL) return;
    vec[level].push_back(root->val);
    levelOrderRec(root->left,vec,level-1);
    levelOrderRec(root->right,vec,level-1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

def find_max(node)
    if node.nil?
        return 0
    end

    return 1 + [find_max(node.left), find_max(node.right)].max
end

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[][]}

def level_recursive(root, output, level) 
  if root.nil?
      return
  end

    output[level] << root.val
    level_recursive(root.left, output, level - 1)
    level_recursive(root.right, output, level - 1)
end

def level_order_bottom(root)
   output = []

    if root.nil?
        return output
    end
    count = find_max(root)
    for i in (0...count)
       output << [] 
    end
    level_recursive(root, output, count - 1)

    return output
end