Reverse Odd Levels of Binary Tree

Naive Approach: Level Order Traversal with Reversal

One straightforward approach is to perform a level order traversal of the binary tree. While traversing, keep track of the current level. When we reach an odd level, store the node values in a temporary array, reverse the array, and then update the node values in the tree with the reversed values.

Pseudocode

function reverseOddLevels(root):
  queue = [root]
  level = 0

  while queue is not empty:
    size = length of queue
    level_values = []
    next_level_nodes = []

    for i from 0 to size - 1:
      node = queue.pop(0)
      level_values.append(node.val)

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

    if level is odd:
      level_values.reverse()
      # Update node values at this level
      queue2 = [root]
      level2 = 0
      while queue2 is not empty:
          size2 = length of queue2
          next_level_nodes2 = []
          index = 0
          for i from 0 to size2 - 1:
              node2 = queue2.pop(0)
              if level == level2 and index < len(level_values):
                node2.val = level_values[index]
                index += 1

              if node2.left:
                  next_level_nodes2.append(node2.left)
              if node2.right:
                  next_level_nodes2.append(node2.right)

          queue2 = next_level_nodes2
          level2 +=1



    queue = next_level_nodes
    level += 1

  return root

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node multiple times, once for the level order traversal, and potentially another time to update the reversed values.
• Space Complexity: O(W), where W is the maximum width of the tree. This is the space required for the queue in the level order traversal. In the worst case (a complete binary tree), W is proportional to N.

Optimal Approach: Recursive In-Place Reversal

A more efficient approach is to use recursion to traverse the tree and reverse the node values in-place. The key idea is to compare the nodes at each odd level and swap their values.

Pseudocode

function reverseOddLevels(root):
  helper(root.left, root.right, 1)
  return root

function helper(node1, node2, level):
  if node1 is null or node2 is null:
    return

  if level is odd:
    swap(node1.val, node2.val)

  helper(node1.left, node2.right, level + 1)
  helper(node1.right, node2.left, level + 1)

Code Implementation

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:
    def helper(node1, node2, level):
        if not node1 or not node2:
            return

        if level % 2 == 1:
            node1.val, node2.val = node2.val, node1.val

        helper(node1.left, node2.right, level + 1)
        helper(node1.right, node2.left, level + 1)

    helper(root.left, root.right, 1)
    return root

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is the space required for the call stack in the recursive function. In the worst case (a skewed tree), H is proportional to N. In the best case (a balanced tree), H is proportional to log N.

Edge Cases

• Empty Tree: If the root is null, return null.
• Single Node Tree: If the tree has only one node, there are no odd levels to reverse, so return the root.
• Perfect Binary Tree: The problem statement specifies that the tree is a perfect binary tree, so we don't need to handle cases where the tree is not complete or balanced.