Problem

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Input:
[1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5

Output:
 return the root of the binary tree [4,5,2,#,#,3,1]

   4
  / \
 5   2
    / \
   3   1

Clarification:

Confused what [4,5,2,#,#,3,1] means? Read more below on how binary tree is serialized on OJ.

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

1
2
3
4
5
6
7

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as [1,2,3,#,#,4,#,#,5].

Solution

So, in the upside-down transformation logic:

  • The left child becomes the parent of the current node.
  • The right child becomes the left leaf of the former left child.
  • The current node becomes the right leaf.

The flipping continues until the root becomes the last left child in the original tree.

Method 1 - Iterative

The process involves restructuring node connections iteratively while traversing top-down.

  1. Keep track of previously processed nodes (prev) and their parent relationships.
  2. For each node:
    • Store its left and right children temporarily.
    • Establish the flipped relationships based on the transformation rules.
  3. Update the pointers recursively or iteratively until all nodes are processed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public TreeNode flipTree(TreeNode root) {
        TreeNode prev = null, prevRight = null, curr = root;

        while (curr != null) {
            TreeNode nextNode = curr.left; // Capture the next node
            curr.left = prevRight;        // Old right becomes new left
            prevRight = curr.right;      // Store current right for use
            curr.right = prev;           // Old parent becomes new right
            
            prev = curr;                 // Update previous node
            curr = nextNode;             // Move to next node
        }
        return prev; // The new root
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def flipTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        prev: Optional[TreeNode] = None
        prev_right: Optional[TreeNode] = None
        curr: Optional[TreeNode] = root

        while curr:
            next_node: Optional[TreeNode] = curr.left # Store next node
            curr.left = prev_right                   # Set new left
            prev_right = curr.right                  # Update prev_right
            curr.right = prev                        # Set new right
            
            prev = curr                              # Move prev and curr
            curr = next_node                         # Proceed to next iteration

        return prev # New root of flipped tree

Complexity

  • ⏰ Time complexity: O(n). The algorithm traverses the tree once, processing each node. Thus, O(n), where n is the total number of nodes.
  • 🧺 Space complexity: O(1). Since the operation happens in-place and uses a constant amount of extra variables, the space complexity is O(1).