We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Odd Levels of Binary Tree

Number: 2493

Difficulty: Medium

Paid? No

Companies: Google, josh technology, J.P. Morgan

Problem Description

Given the root of a perfect binary tree, reverse the node values at each odd level (i.e. level 1, 3, 5, etc.) and return the modified tree. In a perfect binary tree every parent has two children and all leaves are at the same depth.

Key Insights

  • The tree is perfect, which guarantees symmetry.
  • Only the node values at odd levels need to be reversed; even levels remain unchanged.
  • A recursive or BFS approach can be used to traverse the tree while pairing symmetric nodes.
  • For symmetric pairs at an odd level, simply swap their values.
  • The reversal operation can be achieved without needing extra space for storing a full level's nodes.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes since each node is visited once. Space Complexity: O(h) where h is the height of the tree (O(log n) for a perfect binary tree) due to recursion or queue usage.

Solution

The solution uses a recursive approach to traverse the tree in a mirrored fashion. A helper function pairs up nodes that are symmetric relative to the center of the tree. At each recursive call, if the current level is odd, swap the values of the paired nodes. Then, recurse for their child nodes in a mirrored order: left child of the first node with the right child of the second node, and vice versa. This approach guarantees that all symmetric pairs on each odd level have their values reversed.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def reverseOddLevels(self, root: TreeNode) -> TreeNode:
        # Helper function to traverse the tree in a symmetric manner
        def dfs(left_node, right_node, level):
            # Base case: if any node is None, stop recursion.
            if not left_node or not right_node:
                return
            # If the current level is odd, swap the values of the symmetric nodes.
            if level % 2 == 1:
                left_node.val, right_node.val = right_node.val, left_node.val
            # Recursively process the next level in mirrored order.
            dfs(left_node.left, right_node.right, level + 1)
            dfs(left_node.right, right_node.left, level + 1)
        
        # Start the recursive process from the first level
        dfs(root.left, root.right, 1)
        return root
← Back to All Questions