Vertically traverse tree - Feb. 18, 10:00 PM FANG manager - interviewee

verticallyTraverseTree.java

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class TreeNode {
  int val;
  TreeNode left, right;
  public TreeNode(int val) {
    this.val = val;
  }
}

class Solution {
  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left= new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right =new TreeNode(5);
    root.right.left =new TreeNode(8);
    root.right.right =new TreeNode(7);
    
    List<List<Integer>> ans = convertToVertical(root);
    
    for(List<Integer> list : ans) {
      for(Integer val : list) {
        System.out.print(val + ",");
      }
      System.out.println("");
    }
  }
  
  /* 
given a binary tree, output vertically. 
For example, 

        1(0) (3)
      /     \
    2(-1)     3
   / \       / \
4(-2) 5(3)  8   7
-------------------->
*/
  
  public static List<List<Integer>> convertToVertical(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) {
      return res;
    }
    
    int leftMost = getLeftMostIndex(root, 0);  // leftmost 
    
    convertToVerticalHelper(root, res, Math.abs(leftMost));
    
    return res;
  }
  
  /// make sure all nodes - will be
  private static int getLeftMostIndex(TreeNode root, int index) {
    if(root.left == null && root.right == null) { // base case: the node is leaf node
      return index;
    } else if(root == null) {
      return Integer.MAX_VALUE;
    }
    // root - line 35, value 1 getleftmostIndex(node1.left, index - 1)    
    return Math.min(getLeftMostIndex(root.left, index-1), getLeftMostIndex(root.right, index+1));
  }
  
  private static void convertToVerticalHelper(TreeNode root, List<List<Integer>> res, int index) {
    if(root == null) {
      return;
    }
    
    while(res.size()<=index) {  // -> dynamic 
      res.add(new ArrayList<>());
    }
    
    res.get(index).add(root.val);
    
    convertToVerticalHelper(root.left, res, index-1);
    convertToVerticalHelper(root.right, res, index+1);
  }
}



/* 
given a binary tree, output vertically. 
For example, 

       1(0)
      /    \
    2(-1)    3
   / \      / \
4(-2) 5    8   7
    /
   5
  /
  6
  /
 7
-------------------->
4     1 3  7
  2   5
  
 list of list
 [4]
 [2]
 [1, 5, 8] - relax the constraint - 
 [3]
 [7]
 
 Use cases:
 * Order of the conflict can be relaxed
 * Binary tree as an input (null? yes possible and return empty list)
 * values in the node a Integer.MIN_VALUE -> Integer.MAX_VALUE
 */