Binary Tree Upside Down
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 herejavascript
/**
* 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
}
}go
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
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
Hiring now
Linkedin has 196 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Lead Account Executive, Large Customer, Financial Services - LinkedIn Marketing Solutions
Chicago, IL, United States
Director, LinkedIn Pulse Digital Platform
New York, NY, United States
Next question