Reverse Odd Levels of Binary Tree

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree. A binary tree is perfect if all parent nodes have two children and all leaves are on the same level. The level of a node is the number of edges along the path between it and the root node.

For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2]. Return the root of the reversed tree.

Example 1: Input: root = [2,3,5,8,13,21,34] Output: [2,5,3,8,13,21,34] Explanation: The tree has only one odd level. The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.

Example 2: Input: root = [7,13,11] Output: [7,11,13] Explanation: The nodes at level 1 are 13, 11, which are reversed and become 11, 13.

Example 3: Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2] Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1] Explanation: The odd levels have non-zero values. The nodes at level 1 were 1, 2, and are 2, 1 after the reversal. The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.

Constraints:

• The number of nodes in the tree is in the range [1, 2^14].
• 0 <= Node.val <= 10^5
• root is a perfect binary tree.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def reverseOddLevels(root: TreeNode) -> TreeNode:
    if not root:
        return None

    queue = deque([root])
    level = 0

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

        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        if level % 2 != 0:
            values = [node.val for node in level_nodes]
            values.reverse()
            for i in range(level_size):
                level_nodes[i].val = values[i]

        level += 1

    return root

# Example Usage:
# Create the tree from the input [2,3,5,8,13,21,34]
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.left.left = TreeNode(8)
root.left.right = TreeNode(13)
root.right.left = TreeNode(21)
root.right.right = TreeNode(34)

reversed_root = reverseOddLevels(root)

# To print the tree (level order):
def print_tree(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

print_tree(reversed_root) # Output: 2 5 3 8 13 21 34

Naive Solution

The naive solution would involve traversing the tree and identifying the nodes at odd levels. For each odd level, we would store the node values in a temporary array, reverse the array, and then update the node values in the tree with the reversed values. This approach requires extra space for storing the node values at each level.

Optimal Solution

The provided Python code implements an optimal solution to reverse the node values at each odd level of a perfect binary tree. It utilizes a level-order traversal approach using a queue to efficiently process the tree level by level. This ensures that only nodes at the same level are reversed, maintaining the tree's structure and integrity.

Big(O) Run-time Analysis

The time complexity of the reverseOddLevels function is O(N), where N is the number of nodes in the binary tree. This is because the function visits each node exactly once during the level-order traversal. The reversal of node values at odd levels takes O(K) time, where K is the number of nodes at that level. Since the sum of nodes across all levels is N, the overall time complexity remains O(N).

Big(O) Space Usage Analysis

The space complexity is O(W), where W is the maximum width of the binary tree. In the worst-case scenario (a complete binary tree), W would be proportional to N (number of nodes), specifically at the last level. The queue queue stores nodes for the next level, and the level_nodes list stores nodes for the current level being processed, both contributing to the space usage. Therefore, the space complexity is primarily determined by the queue, making it O(W).

Edge Cases

1. Empty Tree: If the input tree is empty (i.e., root is None), the function should return None without any processing.
2. Single Node Tree: If the tree consists of only the root node, there are no odd levels, and the function should return the root node as is.
3. Perfect Binary Tree of Height 1: In this case, level 1 exists and needs to be reversed. The code correctly handles this case.
4. All Node Values are the Same: The reversal should still occur correctly, even if all nodes at a particular odd level have the same value.
5. Large Number of Nodes: The code should be able to handle a large number of nodes (up to 2¹⁴ as specified in the constraints) without exceeding memory limits or causing stack overflow issues.