# Share my java recursive & iterative solution with comments

• ``````public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root==null || root.left==null) { return root; }  // the new root of the upside-down tree
TreeNode newRoot = upsideDownBinaryTree(root.left);
TreeNode newParent = root.left;  // the new parent of current level is originally the left child
newParent.left = root.right;
newParent.right = root;
newParent.right.left = null;  // set original parent's left and right pointer to null, otherwise there will be a loop at the last backtracking level
newParent.right.right = null;
return newRoot;
}
}
``````

As we can see, this is just tail-recursion, so we can easily translate it into iterative version.

``````public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null) { return null; }
List<TreeNode> s = new ArrayList<>();  // our own stack
for (TreeNode p=root; p!=null; p=p.left) { s.add(p); }
for (int i=s.size()-2; i>=0; --i) {
TreeNode oldParent = s.get(i);
TreeNode newParent = oldParent.left;
newParent.left = oldParent.right;
newParent.right = oldParent;
oldParent.left = null; oldParent.right = null;
}
return s.get(s.size()-1);
}
}``````

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