# Explain the question and my solution, Python

• I need to admit that I totally didn't get how to do the "upside-down"

After some struggling and googling, I saw the graph in binary tree representation of trees.

It's not directly the same, but give me a sense of how to do it.

The transform of the base three-node case is like below:

``````                         Root                   L
/  \                  /  \
L    R                R   Root
``````

You can image you grab the L to the top, then the Root becomes it's right node, and the R becomes its left node.

Knowing the base case, you can solve it recursively.

How? You keep finding the left most node, make it upside-down, then make its parent to be its right most subtree recursively.

Here is a small point to be noticed, when you connect the root to the right subtree, you need to make sure you are not copying the original root, otherwise it will become cyclic!

``````def upsideDownBinaryTree(self, root):
if not root or not root.left:
return root
lRoot = self.upsideDownBinaryTree(root.left)
rMost = lRoot
while rMost.right:
rMost = rMost.right
root, rMost.left, rMost.right = lRoot, root.right, TreeNode(root.val)
return root``````

• Java version:

``````public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null || root.left == null)
return root;
TreeNode newRoot = upsideDownBinaryTree(root.left);
TreeNode rightMostIterator = newRoot;
while (rightMostIterator.right != null) {
rightMostIterator = rightMostIterator.right;
}
rightMostIterator.left = root.right;
rightMostIterator.right = new TreeNode(root.val);
return newRoot;
}
}``````

• This post is deleted!

• Actually, you can also return rMost in each iteration such that you don't need to find rMost from the root every time.

``````def upsideDownBinaryTree(self, root):
if not root or not root.left:
return root

def updown(root):
if not root or not root.left:
return root,root

lRoot,rMost = updown(root.left)

rMost.left, rMost.right = root.right, TreeNode(root.val)
return lRoot,rMost.right

result,rMost=updown(root)
return result
``````

• A better version. You don't need to new TreeNode:

``````def upsideDownBinaryTree(self, root):
if not root or not root.left:
return root

def updown(root):
if not root or not root.left:
return root,root

lRoot,rMost = updown(root.left)

rMost.left  = root.right
root.left=None
root.right=None
rMost.right = root

return lRoot,rMost.right

result,rMost=updown(root)
return result
``````

• @orbuluh I really like your solution!
I am just curious about its time complexity.
I think that the worst time complexity for the recursion part would be O(logN) (where n is the number of nodes) and the while loop part is also O(logN) for the worst case. Therefore, the time complexity is going to be O(logN).
Am I understanding it correctly?

Thank you so much!

• Actually, you don't need to track its rightmost leave nor use TreeNode(). Because the rightmost leave is the root.left at current recursive call. Here's the code:

``````    def upsideDownBinaryTree(self, root):
if root and root.left :
res = self.upsideDownBinaryTree(root.left)
root.left.right=root
if root.right :
root.left.left=root.right
root.left =None
root.right=None
return res
else:
return root
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.