Binary Tree Upside Down

Problem

Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Example:

Input: [1,2,3,4,5]

    1

   / \

  2   3

 / \

4   5

Output: return the root of the binary tree [4,5,2,#,#,3,1]

   4

  / \

 5   2

    / \

   3   1  

Solution

We can walk left until no left. During this journey, we store the node in collections for later retrieval. 

One way is to make 2 collections. Use stack for path nodes, and use queue for the branch nodes.

walk from root to leaf, push node to stack, add branch to queue.

pop the stack to building the new tree, poll the queue for the branches.

The time cost is O(height), the space is O(N).

After some observations, we can get rid of the queue to save space.

import java.util.*;
public class UpsideDown {
  public Node upsideDown(Node root) {
    Stack<Node> stem = new Stack<>();
    addNodes(root, stem);
    return buildTree(stem);
  }
  private void addNodes(Node root, Stack<Node> stem) {
    if(root == null) return;
    stem.push(root);
    addNodes(root.left, stem);
  }
  /*
    1
   / \
  2   3
 / \
4   5
        4
       / \
      5   2
         / \
        3   1
  */
  private Node buildTree(Stack<Node> stem) {
    Node root = stem.pop();
    Node curr = root;
    while(!stem.isEmpty()) {
      Node node = stem.pop();
      curr.left = node.right;
      curr.right = node;
      node.left = null;
      node.right = null;
      curr = node;
    }
    return root;
  }
  public static void main(String...args) {
    Node root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)), new Node(3, null, null));
    UpsideDown ud = new UpsideDown();
    ud.printTree(root);
    root = ud.upsideDown(root);
    System.out.println();
    ud.printTree(root);
  }
  private int height(Node root) {
    if(root == null) return 0;
    int lheight = height(root.left);
    int rheight = height(root.right);
    return Math.max(lheight, rheight) + 1;
  }
  private void printTree(Node root) {
    int level = height(root);
    for(int i = 1; i <= level; i++) {
      printGivenLevel(root, i);
      System.out.println();
    }
  }
  private void printGivenLevel(Node root, int level) {
    if(root == null) {
      System.out.print("# ");
      return;
    }
    if(level == 1) {
      System.out.print(root.val + " ");
      return;
    }
    printGivenLevel(root.left, level - 1);
    printGivenLevel(root.right, level - 1);
   
  }
  private static class Node {
    int val;
    Node left;
    Node right;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}

The time cost is O(N), the space cost is O(N).