Case study: Vertically traverse binary tree

Feb. 18, 2020

Introduction

It is my mock interview as an interviewer. I met a manager from FANG company (Facebook, Apple, Netflix, Google), and then I learned surprising a good idea how to write optimal solution for the algorithm. I like to write a short case study on this interview.

Case study

I will add more detail later.

	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
	*/

view raw verticallyTraverseTree.java hosted with ❤ by GitHub

Here is the gist.