Skip to content

156. Binary Tree Upside Down 👎

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  TreeNode* upsideDownBinaryTree(TreeNode* root) {
    if (root == nullptr || root->left == nullptr)
      return root;

    TreeNode* newRoot = upsideDownBinaryTree(root->left);
    root->left->left = root->right;  // 2's left = 3 (root's right)
    root->left->right = root;        // 2's right = 1 (root)
    root->left = nullptr;
    root->right = nullptr;
    return newRoot;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null || root.left == null)
      return root;

    TreeNode newRoot = upsideDownBinaryTree(root.left);
    root.left.left = root.right; // 2's left = 3 (root's right)
    root.left.right = root;      // 2's right = 1 (root)
    root.left = null;
    root.right = null;
    return newRoot;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def upsideDownBinaryTree(self, root: TreeNode | None) -> TreeNode | None:
    if not root or not root.left:
      return root

    newRoot = self.upsideDownBinaryTree(root.left)
    root.left.left = root.right  # 2's left = 3 (root's right)
    root.left.right = root  # 2's right = 1 (root)
    root.left = None
    root.right = None
    return newRoot

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  TreeNode* upsideDownBinaryTree(TreeNode* root) {
    TreeNode* prevRoot = nullptr;
    TreeNode* prevRightChild = nullptr;

    while (root != nullptr) {
      TreeNode* nextRoot = root->left;  // Cache the next root.
      root->left = prevRightChild;
      prevRightChild = root->right;
      root->right = prevRoot;
      prevRoot = root;  // Record the previous root.
      root = nextRoot;  // Update the root.
    }

    return prevRoot;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public TreeNode upsideDownBinaryTree(TreeNode root) {
    TreeNode prevRoot = null;
    TreeNode prevRightChild = null;

    while (root != null) {
      TreeNode nextRoot = root.left; // Cache the next root.
      root.left = prevRightChild;
      prevRightChild = root.right;
      root.right = prevRoot;
      prevRoot = root; // Record the previous root.
      root = nextRoot; // Update the root.
    }

    return prevRoot;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def upsideDownBinaryTree(self, root: TreeNode | None) -> TreeNode | None:
    prevRoot = None
    prevRightChild = None

    while root:
      nextRoot = root.left  # Cache the next root.
      root.left = prevRightChild
      prevRightChild = root.right
      root.right = prevRoot
      prevRoot = root  # Record the previous root.
      root = nextRoot  # Update the root.

    return prevRoot