# 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: Optional[TreeNode]) -> Optional[TreeNode]: 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) { TreeNode* nextRoot = root->left; // Cache next root root->left = prevRightChild; prevRightChild = root->right; root->right = prevRoot; prevRoot = root; // Record previous root root = nextRoot; // Update 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 next root root.left = prevRightChild; prevRightChild = root.right; root.right = prevRoot; prevRoot = root; // Record previous root root = nextRoot; // Update root } return prevRoot; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: prevRoot = None prevRightChild = None while root: nextRoot = root.left # Cache next root root.left = prevRightChild prevRightChild = root.right root.right = prevRoot prevRoot = root # Record previous root root = nextRoot # Update root return prevRoot