Binary Tree upside Down

XXX. Upside Down Binary Tree

Tree

Recursion

Problem Statement:

Given the root of a binary tree, transform it into an "upside down" binary tree where:

• The original left child becomes the new root.
• The original root becomes the right child of the new root.
• The original right child becomes the left child of the new root.

Return the new root of the tree after performing this transformation.

Algorithm:

The algorithm uses recursion to traverse the tree and perform the transformation:

1. Recursively call the function on the left child until reaching the leftmost node (new root).
2. Transform the tree:
   • Set the left child of the current node to its original right child.
   • Set the right child of the current node to the original root.
3. Set the left and right children of the original root to null to avoid cycles.
4. Return the new root after processing all nodes.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.

Java Implementation:

public class Solution {

    public TreeNode upsideDownBinaryTree(TreeNode root) {
        // Base case: if the root is null or a leaf node, return it
        if (root == null || (root.left == null && root.right == null))
            return root;

        // Recursively transform the left subtree
        TreeNode newRoot = upsideDownBinaryTree(root.left);

        // Transform the current node's left and right children
        root.left.left = root.right; // Original right child becomes left child
        root.left.right = root;      // Original root becomes right child

        // Disconnect the original root's left and right children
        root.left = null;
        root.right = null;

        // Return the new root
        return newRoot;
    }
}