2415. Reverse Odd Levels of Binary Tree

#binary-tree

Problem

Reverse Odd Levels of Binary Tree - LeetCodeLeetCode

Intuition

Explained in the code it self

Time Complexity

O(V + E), standard BFS
O(V * number of odd levels) // Reversing the values
Total = O(V + E) + O(v * number of odd levels) = O(V + E)

Since the O(V * number of odd levels) is smaller than O(V + E) we do not consider that

Space Complexity

 O(V * number of odd level)
 At every odd level, we store the values to reverse the order

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        // TC: 
        // -> O(V + E), standard BFS
        // -> O(V * number of odd levels)
        // O(V + E) + O(v * number of odd levels) = O(V + E)

        // Space Complexity: O(V * number of odd level)

        if(root == null) return root;
        
        // Standard BFS traversal
        Queue<TreeNode> q = new ArrayDeque<>();
        TreeNode curr = root;

        q.offer(curr);

        int level = 0;

        while(!q.isEmpty()) {
            int n = q.size();
            // Pre Incrementing cause, we need to reverse the vals before odd levels
            // get processed
            level++;

            for(int i=0;i<n;i++) {
                TreeNode node = q.poll();

                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }

            // Check if the level is odd and the q is not empty
            if(level % 2 == 1 && !q.isEmpty()) {
                // Create a array to store values in the q
                int[] vals = new int[q.size()];
                int i = 0;

                // traverse through the from top to bottom 
                // Store the values in "vals"
                for(TreeNode n1:q) vals[i++] = n1.val;

                // Since we need to reverse the values
                // we need to start filling the values in reverse
                // So setting the index to start from last value in vals
                int j = q.size() - 1;

                // Traverse through the q and update the values
                // in reverse order using "j" index
                for(TreeNode n1:q) n1.val = vals[j--];
            }
        }
        // Since we are just traversing and not changing the root itself
        // return the root
        return root;
    }
}