deepSWE.io

Binary Tree Upside Down

Trees

Problem Statement

Given the `root` of a binary tree, turn the tree upside down and return the new root. You can assume that every right node has a sibling (a left node with the same parent) and has no children.

Example

Original

Upside Down

Algorithm Explanation

We can solve this problem recursively. The main idea is to traverse to the leftmost node, which will become the new root. Then, as we backtrack, we rearrange the pointers.

Algorithm Steps

Base Case: If the current node is null or a leaf, we return it as it is.
Recursive Call: Recursively call the function on the left child. This will return the new root of the upside-down tree.
Rearrange Pointers: Once the recursive call returns, we are at a parent node. We set its left child's left pointer to the parent's right child, and the left child's right pointer to the parent itself.
Clear Old Pointers: After rearranging, we set the original parent's left and right pointers to null to avoid cycles.

Start

Starting the process.

Binary Tree Upside Down Solution


class Solution:
    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Base case: if the root is null or it's a leaf, return the root
        if not root or not root.left:
            return root
        
        # Recursively call on the left child to find the new root
        new_root = self.upsideDownBinaryTree(root.left)
        
        # Rearrange pointers
        root.left.left = root.right
        root.left.right = root
        
        # Clear the original pointers
        root.left = None
        root.right = None
        
        return new_root