We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Upside Down

Number: 156

Difficulty: Medium

Paid? Yes

Companies: LinkedIn

Problem Description

Given the root of a binary tree, transform the tree by turning it upside down. In this transformation, every original left child becomes the new root, the original root becomes the new right child, and the original right child becomes the new left child. The transformation is applied level by level and it is guaranteed that every right node has a sibling and no children.

Key Insights

  • The transformation is easier to perform using recursion, processing from the bottom-most left child up.
  • The base case is when the current node is null or when it doesn’t have a left child.
  • As the recursion unwinds, reassign pointers: the left child’s left becomes the original right, and the left child’s right becomes the current node.
  • After reassignments, remove the original left and right pointers to avoid cycles.
  • The new root is determined by the left-most node in the original tree.

Space and Time Complexity

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

Solution

We use a recursive approach to flip the tree. We start by recursively reaching the left-most node, which will ultimately be the new root. As we return from recursion, we perform the following steps for the current node:

  1. Set the left child’s left pointer to the original right child.
  2. Set the left child’s right pointer to the current node.
  3. Nullify the current node’s left and right pointers to break old connections. This method ensures that each level of the tree is correctly transformed, resulting in the upside-down binary tree.

Code Solutions

# 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

def upsideDownBinaryTree(root):
    # Base case: if there is no node or no left child, return the node
    if not root or not root.left:
        return root
    # Recursively process the left subtree
    newRoot = upsideDownBinaryTree(root.left)
    # Reassign pointers:
    # Original left child's left becomes original right child
    root.left.left = root.right
    # Original left child's right becomes the current node
    root.left.right = root
    # Remove old links to avoid cyclic references
    root.left = None
    root.right = None
    return newRoot

# Example usage:
# Construct the tree: [1,2,3,4,5]
# Tree construction can be done as required before calling upsideDownBinaryTree(root)
← Back to All Questions