Problem of The Day: Reverse Odd Levels of Binary Tree

5 min read 1004 words

Problem Statement

leetcode problem link

Solution [Accepted]

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        q = deque()
        q.append(root)
        level = -1
        while q:
            n = len(q)
            level += 1
            if level % 2: # odd level
                temp = []
                for _ in range(n):
                    node = q.popleft()
                    if node:
                        temp.append(node)
                        q.append(node.left)
                        q.append(node.right)
                l, r = 0, len(temp) - 1
                while l < r:
                    temp[l].val, temp[r].val = temp[r].val, temp[l].val
                    l += 1
                    r -= 1
            else:
                for _ in range(n):
                    node = q.popleft()
                    if node:
                        q.append(node.left)
                        q.append(node.right)

        return root

DFS Approach

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public void Helper(TreeNode leftNode, TreeNode rightNode, int level) {
        if (leftNode == null || rightNode == null) {
            return;
        }
        if (level % 2 == 0) {
            var temp = leftNode.val;
            leftNode.val = rightNode.val;
            rightNode.val = temp;
        }
        Helper(leftNode.left, rightNode.right, level + 1);
        Helper(leftNode.right, rightNode.left, level + 1);

    }
    public TreeNode ReverseOddLevels(TreeNode root) {
        Helper(root.left, root.right, 0);
        return root;
    }
}

Editorial

Approach 1: Depth-First Search

class Solution:
    def reverseOddLevels(self, root) -> TreeNode:
        self.__traverse_DFS(root.left, root.right, 0)
        return root

    def __traverse_DFS(self, left_child, right_child, level):
        if left_child is None or right_child is None:
            return
        # If the current level is odd, swap the values of the children.
        if level % 2 == 0:
            temp = left_child.val
            left_child.val = right_child.val
            right_child.val = temp

        self.__traverse_DFS(left_child.left, right_child.right, level + 1)
        self.__traverse_DFS(left_child.right, right_child.left, level + 1)

Approach 2: Breadth-First Search

class Solution:
    def reverseOddLevels(self, root):
        if not root:
            return None  # Return None if the tree is empty.

        queue = [root]  # Start BFS with the root node.
        level = 0

        while queue:
            size = len(queue)
            current_level_nodes = []

            # Process all nodes at the current level.
            for _ in range(size):
                node = queue.pop(0)
                current_level_nodes.append(node)

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

            # Reverse node values if the current level is odd.
            if level % 2 == 1:
                left, right = 0, len(current_level_nodes) - 1
                while left < right:
                    tmp = current_level_nodes[left].val
                    current_level_nodes[left].val = current_level_nodes[
                        right
                    ].val
                    current_level_nodes[right].val = tmp
                    left += 1
                    right -= 1

            level += 1

        return root  # Return the modified tree root.