Coding

Binary Tree Upside Down

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given the root of a binary tree, turn the tree upside down and return the new root. You can turn a binary tree upside down with the following steps:

The original left child becomes the new root.
The original root becomes the new right child.
The original right child becomes the new left child. The mentioned steps are done level by level. It is guaranteed that every right node has a sibling (a left node with the same parent) and has no children.

Input: root = [1,2,3,4,5] Output: [4,5,2,null,null,3,1]

Input: root = [1] Output: [1]

Input : root = [5,3,null,1,null,6,null,2,null,4]

The number of nodes in the tree will be in the range [0, 10].
0 <= Node.val <= 10
Every right node in the tree has a sibling (a left node that shares the same parent).
Every right node in the tree has no children.

cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        // Your code goes here
    }
};

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        // Your code goes here   
    }
}

python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def upsideDownBinaryTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        # Your code goes here

javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var upsideDownBinaryTree = function(root) {
    // Your code goes here
};

csharp

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode UpsideDownBinaryTree(TreeNode root) {
        // Your code goes here
    }
}

func upsideDownBinaryTree(root *TreeNode) *TreeNode {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Walk down the original left spine while preserving the next left child.
02Make the previous original right child the current node's new left child.
03Make the previous original parent the current node's new right child.
04Clear the old links and return the last processed node as the new root.

Reference answer

Iterate down the original left spine with current, while keeping previousParent and previousRight. Before rewiring a node, save nextLeft = current.left and nextRight = current.right. Set current.left = previousRight and current.right = previousParent; then advance previousParent = current, previousRight = nextRight, and current = nextLeft. When current becomes null, previousParent is the new root. The saved references are essential because assigning the new children destroys the original links needed for the next level. The given structural guarantee means each original right child is a leaf-like sibling and can safely become the next node's left child. Every node on the transformed spine is processed once, so time is O(h) for this constrained shape and extra space is O(1); a recursive formulation uses O(h) call-stack space.

Then expect these follow-ups

How would you write the recursive version?
Tests: recursive rewiring
Why is the structural guarantee about right children necessary?
Tests: preconditions

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question