Java recursive (O(logn) space) and iterative solutions (O(1) space) with explanation and figure


  • 162
    Y

    This is not a very intuitive problem for me, I have to spent quite a while drawing figures to understand it. As shown in the figure, 1 shows the original tree, you can think about it as a comb, with 1, 2, 4 form the bone, and 3, 5 as the teeth. All we need to do is flip the teeth direction as shown in figure 2. We will remove the link 1--3, 2--5, and add link 2--3, and 4--5. And node 4 will be the new root.

    As the recursive solution, we will keep recurse on the left child and once we are are done, we found the newRoot, which is 4 for this case. At this point, we will need to set the new children for node 2, basically the new left node is 3, and right node is 1. Here is the recursive solution:

    enter image description here

    Recursive:

    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null || root.left == null) {
            return root;
        }
        
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        root.left.left = root.right;   // node 2 left children
        root.left.right = root;         // node 2 right children
        root.left = null;
        root.right = null;
        return newRoot;
    }
    

    For the iterative solution, it follows the same thought, the only thing we need to pay attention to is to save the node information that will be overwritten.

    iterative

    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode curr = root;
        TreeNode next = null;
        TreeNode temp = null;
        TreeNode prev = null;
        
        while(curr != null) {
            next = curr.left;
            
            // swapping nodes now, need temp to keep the previous right child
            curr.left = temp;
            temp = curr.right;
            curr.right = prev;
            
            prev = curr;
            curr = next;
        }
        return prev;
    }  
    

  • 4
    C

    I think your explanation is the clearest in this thread.


  • 7

    Nice write-up, but since the tree is not a typical tree (more like a trunk), I don't think the recursive solution is O(logn) space -- it should be O(n).


  • 2
    G

    Really smart answer and detailed explanation. Thanks for sharing.


  • 0
    F

    @feyhi True. In other words, the height of the tree is more like n,not log(n) in this problem.


  • 0
    K

    @yfcheng Nice iterative solution. Here's my iterative solution. I'm using more variables than I need:

    public class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            
            TreeNode curr = root;
            TreeNode right = root.right;
            TreeNode left = root.left;
            
            root.left = null;
            root.right = null;
            
            TreeNode parent = null;
            TreeNode parentOriginalLeft = null;
            TreeNode parentOriginalRight = null;
            while (left != null) {
                parent = left;
                parentOriginalLeft = parent.left;
                parent.left = right;
                parentOriginalRight = parent.right;
                parent.right = curr;
                
                curr  = parent;
                left  = parentOriginalLeft;
                right = parentOriginalRight;
            }
            
            return curr;
        }
    }
    

  • 0
    W

    Thanks for explaining using diagram. This helps a lot.


  • 0

    Thumb UP. Thank you for the clear explanation and process of thoughts.

    I think for the recursive space, Should it be O(depth of tree) than O(logN) since it's random binary tree?


  • 2

    Sharing my very similar iterative solution here:

    class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            TreeNode prev = null, gift = null;
            while (root != null) {
                TreeNode next = root.left;
                root.left = gift;
                gift = root.right;
                root.right = prev;
                prev = root;
                root = next;
            }
            return prev;
        }
    }
    

    Also I got a pic that is not so good but helped me in the process of coming up with the solution:

    The primary structure of the code is very similar to the Reverse Linked List problem, so it should not be so hard to understand.


  • 0
    L

    Iterative way is from top to bottom, recursive way is from bottom to top.


Log in to reply
 

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