Facebook Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
5
of 5 vote

When you map the nodes to a coordinate system and sort the nodes by X-Coordinate (if X coordinate is equal, sort it by Y-coordinate), then you will get the answer in the right order.
Root will (0,0).
Left turn will be (x-1,y+1) and right turn will be (x+1,y+1)
In the above example, 6 is mapped to (0,0) , 3 is mapped to (-1,1) and 1 is mapped to (0,2).

Time complexity O(NLOGN) using priority queues
space complexity is O(N).

public Node(Node left, Node right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }
     class NodePriority implements Comparable<NodePriority>{
        private final Node node;
        private final int x;
        private final int y;
        public NodePriority(Node n, int x,int y) {
            this.node = n;
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(NodePriority o) {
            if(this.x == o.x) return this.y - o.y;
            return this.x - o.x;
        }
        public Node getNode(){
            return node;
        }
    }

    static PriorityQueue<NodePriority> pq4Nodes = new PriorityQueue<>();
    
    public  static void processNodesByColumns(Node node, int x,int y) {
        if(node == null) return;
        pq4Nodes.add(new NodePriority(node, x,y));
        processNodesByColumns(node.left,x-1,y+1);
        processNodesByColumns(node.right,x+1,y+1);

    }

    public static void main(String[] args) {
        Node n9  = new Node(null,null,9);
        Node n7  = new Node(null,null,7);
        Node n1  = new Node(null,null,1);
        Node n8  = new Node(null,null,8);
        
        Node n2  = new Node(null,n7,2);
        Node n5  = new Node(n9,n2,5);
        Node n3  = new Node(n5,n1,3);
        
        Node n0  = new Node(n8,null,0);
        Node n4  = new Node(null,n0,4);
        
        Node n6  = new Node(n3,n4,6);
        processNodesByColumns(n6, 0,0);
        while(!pq4Nodes.isEmpty()) {
            NodePriority head  = pq4Nodes.poll();
            System.out.println(head.getNode().value);
        }
        
    }

- naren February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

My solution:
Complexity: O(n^2)
Space: O(n)

public class Node {
    public Node left;
    public Node right;
    public int index;
    public int value;

    public Node(Node left, Node right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }
}

private int minLeft = 0;
private int maxRight = 0;

public void showTree(Node root) {
    // set index to all node in tree
    // and save left most and right most index
    // note that index may be negative
    root.index = 0;
    setIndex(root);

    // from left most to right most index
    // we using bfs to go through the tree
    // if a node index have same index,
    // print this node's value
    for (int i = minLeft; i <= maxRight; i++) {
        // we init a queue
        Queue<Node> queue = new ArrayDeque<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node top = queue.poll();
            if (top.index == i) {
                System.out.print(top.value + " ");
            }
            if (top.left != null) {
                queue.add(top.left);
            }
            if (top.right != null) {
                queue.add(top.right);
            }
        }
    }
}

private void setIndex(Node current) {
    minLeft = Math.min(minLeft, current.index);
    maxRight = Math.max(maxRight, current.index);

    // left node's index = father's index - 1
    if (current.left != null) {
        current.left.index = current.index - 1;
        setIndex(current.left);
    }

    // right node's index = father's index + 1
    if (current.right != null) {
        current.right.index = current.index + 1;
        setIndex(current.right);
    }
}

- techinterviewquestion.com February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

My solution is a little bit more optimal in time - could be O(n) or O(nlog) depending on the sort algorithm used to sort HashMap. In this solution I use TreeMap, so complexity is O(nlogn) time and O(n) space.
The idea is to traverse root, right, left the tree and each time you go left to hash current element with parent hash - 1, and when you go right to hash with parent hash + 1.
Here is some impl. As I mentioned above in case I use ordinary HashMap with no order characterisitcs and sort hash keys with counting sort by hash value, time complexity could optimize to O(n)

TreeMap<Integer,ArrayList<TreeNode>> tree = new TreeMap<>();
 void verticalTraverse(TreeNode root, int pos) {
	    	if(root == null)
	    		return;	    	
	    	if (!tree.containsKey(pos))     	
	    		tree.put(pos,new ArrayList<TreeNode>());
	    	tree.get(pos).add(root);		    	
	    	verticalTraverse(root.right, pos + 1);
	    	verticalTraverse(root.left, pos - 1);
	    	
	    }

- EPavlova February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Actually there is a problem with my code above - order is not kept

- EPavlova February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's my Python 3.5 solution using a two-dimensional dict (hash table):

from collections import namedtuple

Node = namedtuple('Node', ['left', 'value', 'right'])

def merge_columns(columns1, columns2):
    return {
        column_index: {
            **columns1.get(column_index, {}),
            **columns2.get(column_index, {}),
        }
        for column_index in {*columns1.keys(), *columns2.keys()}
    }

def collect_columns(node, column_index=0, depth=0):
    """
    Create a two-dimensional dict, indexed first by the left/right
    position of each column (starting at zero for the root node),
    then by the depth of the node (starting at zero and
    increasing by one for each level)
    """
    left = collect_columns(
        node.left, 
        column_index - 1, 
        depth + 1
    ) if node.left else {}
    right = collect_columns(
        node.right, 
        column_index + 1, 
        depth + 1
    ) if node.right else {}
    columns = { column_index: { depth: node.value } }
    columns = merge_columns(columns, left)
    columns = merge_columns(columns, right)
    return columns

def print_tree(root):
    columns = collect_columns(root)
    print(' '.join(
        str(columns[index][depth])
        for index in sorted(columns.keys())
        for depth in sorted(columns[index].keys())
    ))

root = Node(
    Node(
        Node(
            Node(None, 9, None),
            5,
            Node(
                None,
                2,
                Node(None, 7, None)
            )
        ),
        3,
        Node(None, 1, None)
    ),
    6,
    Node(
        None,
        4,
        Node(
            Node(None, 8, None),
            0,
            None
        )
    )
)
print_tree(root)

Time complexity: O(n log n) since collect_columns is called once per node (total n times), and merge_columns takes at most O(log n) time (iterates once per tree column at most).
Space complexity: O(n) since at most one new hash table is created per node (if each node has its own column), and nodes are stored only once.

- takepwn February 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another similar approach with better complexity.

1. Mark each node with Number of left turns + right turns. (O(n))

2. Walk the tree and insert nodes into a max heap with key - (left turns - right turns) - O(n) + O(heapify) -> worst case -> O(n*log(n))

3. Pop all elements from heap & print -> O(n*log(n))

Cheers!

- Vamsi February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the working code

public static void main(String[] args){

Node node7 = new Node(7, null, null);
Node node2 = new Node(2, null, node7);
Node node9 = new Node(9, null, null);
Node node5 = new Node(5, node9, node2);
Node node1 = new Node(1, null, null);
Node node3 = new Node(3, node5, node1);
Node node8 = new Node(8, null, null);
Node node0 = new Node(0, node8, null);
Node node4 = new Node(4, null, node0);
Node node6 = new Node(6, node3, node4);

Map<Integer, List<Node>> result=getIndexedTree(node6);
_printTreeVertically(result);

}


public static Map<Integer, List<Node>> getIndexedTree(Node root){
Map<Integer, List<Node>> result = new HashMap<>();
Map<Node, Integer> mapIndex = new HashMap<>();
//_buildTreeVertically(root, 0, result);

Queue<Node> queue = new LinkedList<>();
queue.add(root);
mapIndex.put(root, 0);

while(!queue.isEmpty()){
Node node = queue.poll();
_putNodeNIndex(result, node, mapIndex.get(node));
int parentIndex = mapIndex.get(node);
if(node.leftChild !=null){
mapIndex.put(node.leftChild, parentIndex-1);
queue.add(node.leftChild);
}
if(node.rightChild !=null){
mapIndex.put(node.rightChild, parentIndex+1);
queue.add(node.rightChild);
}
}
return result;
}

private static void _putNodeNIndex(Map<Integer, List<Node>> map, Node node, int index){
if(map.get(index) == null){
map.put(index, new ArrayList<Node>());
}
map.get(index).add(node);
}

private static void _printTreeVertically(Map<Integer, List<Node>> result){

//Find the smallest index in the map "result"
int lowestIndex=Integer.MAX_VALUE;
for(Integer i:result.keySet()){
lowestIndex=Math.min(lowestIndex, i);
}

while(result.get(lowestIndex) !=null){
List<Node> nodes = result.get(lowestIndex++);

for(Node node:nodes){
System.out.print(node.value + " ");
}
}

}

- Raj February 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in C# Time complexity O(N) Space (N) the idea is to use a column ID to identify each column the root is column 0 if we move left column decrease by one if we move right column increase. The algorithm uses a bucket sort to store the items in the corresponding column; We use a first past O(N) to get the min and max values of columns and a second pass to store each value in the corresponding bucket position; another pass to generate the final result;

public List<int> GetByColumns(TreeNode root)
{
    var t = GetColumnLimits(root);
    int min = Math.Abs(t.Item1);
    int max = t.Item2;
            
    List<int>[] bucket = new List<int>[min + max + 1];
    for (int i = 0; i < bucket.Length; i++)
        bucket[i] = new List<int>();

    var stack = new Stack<TreeNode>();
    var columns = new Stack<int>();
    stack.Push(root);
    columns.Push(0);

    // Traversal the tree and add the column in the corrsponding bucket;
    while (stack.Count > 0)
    {
        var node = stack.Pop();
        var value = columns.Pop();
        int index = min + value;
        bucket[index].Add(node.Value);

        if (node.Left != null)
        {
            stack.Push(node.Left);
            columns.Push(value - 1);
        }
        if (node.Right != null)
        {
            stack.Push(node.Right);
            columns.Push(value + 1);
        }
    }

    var result = new List<int>();
    foreach (var list in bucket)
        result.AddRange(list);
    return result;
}

private Tuple<int, int> GetColumnLimits(TreeNode root)
{
    var stack = new Stack<TreeNode>();
    var columns = new Stack<int>();
    int min = int.MaxValue;
    int max = int.MinValue;

    stack.Push(root);
    columns.Push(0);
    while (stack.Count > 0)
    {
        var node = stack.Pop();
        var column = columns.Pop();
        min = Math.Min(min, column);
        max = Math.Max(max, column);

        if (node.Left != null)
        {
            stack.Push(node.Left);
            columns.Push(column - 1);
        }
        if (node.Right != null)
        {
            stack.Push(node.Right);
            columns.Push(column + 1);
        }
    }

    return Tuple.Create(min, max);
}

- hnatsu February 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution in Python

def column_printer(tree):

    node_by_column = {}

    min_column = 0
    max_column = 0

    traverse_stack = [(tree, 0)]    

    while len(traverse_stack) > 0:  

        node, column = traverse_stack.pop()

        if column not in node_by_column: 
            node_by_column[column] = []     

        node_by_column[column].append(node)

        for n, d in [(node.left, -1), (node.right, 1)]:
            if n is not None:
                traverse_stack.append((n, column + d))
                min_column = min(column + d, min_column)
                max_column = max(column + d, max_column)
    
    result = []

    for i in xrange(min_column, max_column + 1):
        result += [str(x.value) for x in node_by_column[i]]

    print ",".join(result)

- sd123 February 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is result if input is

# 1
# 2 3
# 4 5 6 7

- tangalai February 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, implementation, O(n log n)

void printTreeColumnOrder(Node* root) {
	map<int, vector<int>> m;
	map<int, vector<int>>::iterator it;
	vector<int> arr;
	queue<pair<Node*, int>> q;
	Node* node;
	int i;

	q.push(make_pair(root, 0));
	while (!q.empty()) {
		node = q.front().first;
		i = q.front().second;
		q.pop();

		if (node == NULL) continue;

		it = m.find(i);
		if (it == m.end()) {
			arr.clear();
			arr.push_back(node->val);
			m.insert(make_pair(i, arr));
		} else {
			it->second.push_back(node->val);
		}

		q.push(make_pair(node->left, i - 1));
		q.push(make_pair(node->right, i + 1));
	}

	for (it = m.begin(); it != m.end(); it++) {
		for (i = 0; i < it->second.size(); i++) {
			cout << it->second[i] << " ";
		}
	}
	cout << "\n";
}

- kyduke February 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Pre-Order traversal:

template<class T>
void Tree<T>::PrintTreeColumns()
{
	map<long, vector<T>*> columns;
	// Use In-Order traversal to print node values
	if (m_root) {
		vector<T>* list = new vector<T>();
		list->push_back(m_root->Item());
		columns.emplace(0, list);
		PrintColumns(m_root, 0, columns);
		for (map<long, vector<T>*>::iterator it = columns.begin(); it != columns.end(); it++)
			for (vector<T>::iterator it1 = it->second->begin(); it1 != it->second->end(); it1++)
				cout << *it1 << ", ";
		cout << endl;
	}
}
template<class T>
void Tree<T>::AddToColumn(T value, long column, map<long, vector<T>*>& columns)
{
	if (columns.find(column) == columns.end())
	{
		vector<T>* list = new vector<T>();
		list->push_back(value);
		columns.emplace(column, list);
	} else
		columns[column]->push_back(value);
}
template<class T>
void Tree<T>::PrintColumns(Node<T> *node, long column, map<long, vector<T>*>& columns)
{
	// Use Pre-Order traversal
	if (node) {
		if (node->Left())
			AddToColumn(node->Left()->Item(), column - 1, columns);
		if (node->Right())
			AddToColumn(node->Right()->Item(), column + 1, columns);
		PrintColumns(node->Left(), column - 1, columns);
		PrintColumns(node->Right(), column + 1, columns);
	}
}

- funcoolgeek March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this solution

#include <stdio.h>
#include <stdlib.h>

typedef struct _tree
{
	int data;
	_tree *left;
	_tree *right;
}tree;

#define SIZE	10
int l, r; // for simplicity get help of global variable

int arr[10] = { 6, 3, 4, 5, 1, 0, 9, 2, 8, 7 };

void getIndex(tree *root, int *left, int *right){
	if (root == NULL) return;
	if (l > left) l = left;
	if (r < right) r = right;
	getIndex(root->left, left - 1, right);
	getIndex(root->right, left, right + 1);
}
void colDisp(tree* root, int col){
	if (root == NULL) return;
	if (col == 0) printf("%d ", root->data);
	colDisp(root->left, col + 1);
	colDisp(root->right, col - 1);
}
int main(int argc, char** argv){
	tree *root = NULL;
	/*assumed tree get prepared*/
	//tree *root = prepBinaryTree(arr, SIZE);	
	getIndex(root, 0, 0);
	printf("\n%d %d\n", l, r);
	for (int i = l; i <= r; i++)
		colDisp(root, i);
	return 0;
}

outPut:: 9 5 3 2 6 1 7 4 8 0

- praveen pandit March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeMap;
import java.util.TreeSet;

class TreeSetComp implements Comparator<TreeColumnData>
{

	@Override
	public int compare(TreeColumnData o1, TreeColumnData o2) {
		// TODO Auto-generated method stub
		
		if(o1.height>o2.height)
		return 1;
		else
			return -1;
	}
	
}

class TreeColumnData
{
	int width;
	int height;
	int data;
	
	TreeColumnData(int w,int h,int d)
	{
		this.width=w;
		this.height=h;
		this.data=d;
	}
}


class TreeNode {
	int data;
	TreeNode leftChild;
	TreeNode rightChild;

	TreeNode(int data, TreeNode left, TreeNode right) {
		this.data = data;
		this.leftChild = left;
		this.rightChild = right;
	}
}


public class TreeTraversals
{

TreeMap<Integer,TreeSet> colTreeMap=new TreeMap<>();

	//program to print the elements in Tree in a column wise manner 
	//The root node is passed with height=1 and width=0
	//Each node is called recursively and the total attributes viz the data of each node, height and width are maintained
	//Sort the data structure based on width-> ascending order and for same width sort ->ascending order of height
	//print the data
	public void columnWisePrint(TreeNode head,int width,int height)
	{
		if(head==null)
		{
			return;
		}
		
		else
		{
			TreeColumnData tcd=new TreeColumnData(width, height, head.data);
			if(colTreeMap.get(width)==null)
			{
				
				TreeSet<TreeColumnData> colTreeSet=new TreeSet<>(new TreeSetComp());
				colTreeSet.add(tcd);
				colTreeMap.put(width, colTreeSet);
				
			}
			
			else
			{
				TreeSet<TreeColumnData> colTreeSet =colTreeMap.get(width);
				colTreeSet.add(tcd);
			}
			
			columnWisePrint(head.leftChild,width-1,height+1);
			columnWisePrint(head.rightChild,width+1,height+1);
			
		}
	}
	
	public static void main(String[] args) {

		TreeNode rootNode0 = new TreeNode(1, null, null);
		TreeNode rootNode1 = new TreeNode(4, null, null);
		TreeNode rootNode2 = new TreeNode(3, rootNode0, rootNode1);
		TreeNode rootNode3 = new TreeNode(5, null, null);
		TreeNode rootNode4 = new TreeNode(9, null, null);
		TreeNode rootNode5 = new TreeNode(7, rootNode3, rootNode4);
		TreeNode rootNode6 = new TreeNode(6, rootNode2, rootNode5);
		TreeTraversals tt = new TreeTraversals();
		
		tt.columnWisePrint(rootNode6, 0, 1);
		for(int ts: tt.colTreeMap.keySet())
		{
			TreeSet tsRes= tt.colTreeMap.get(ts);
			Iterator i=tsRes.iterator();
			while(i.hasNext())
			{
				TreeColumnData tcd =(TreeColumnData) i.next();
				System.out.println("Width->"+tcd.width+" Height->"+tcd.height+" Data->"+tcd.data);
			}
		}
		
	
}
}

- Vamsi Kidambi March 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

class Node {
int data;
Node left;
Node right;

Node(int i) {
this.data = i;
this.left = null;
this.right = null;
}
}

public class PrintColumnOrder {

static void printInOrder(Node n) {
if (n == null)
return;
else {
printInOrder(n.left);
System.out.print(n.data + " ");
printInOrder(n.right);
}
}

static TreeMap cMap;

static void addColumn(Node n, int col) {
if (n == null)
return;
if (cMap.containsKey(col)) {
ArrayList<Integer> list = (ArrayList<Integer>) (cMap.get(col));
list.add(n.data);
} else {
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(n.data);
cMap.put(col, al);
}

addColumn(n.left, col - 1);
addColumn(n.right, col + 1);
}

static void pritColumnOrder(Node n) {
cMap = new TreeMap<Integer, List<Integer>>();
addColumn(n, 0);

Set<Map.Entry<Integer, ArrayList<Integer>>> s = cMap.entrySet();
for (Entry e : s) {
ArrayList<Integer> al = (ArrayList<Integer>) e.getValue();
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
System.out.println();
}

}

public static void main(String args[]) {

Node root = new Node(6);
root.left = new Node(3);
root.right = new Node(4);
root.left.left = new Node(5);
root.left.right = new Node(1);
root.left.left.left = new Node(9);
root.left.left.right = new Node(2);
root.left.left.right.right = new Node(7);
root.right.right = new Node(0);
root.right.right.left = new Node(8);
printInOrder(root);
System.out.println();
pritColumnOrder(root);
}
}

- shailendra verma March 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

class Node {
int data;
Node left;
Node right;

Node(int i) {
this.data = i;
this.left = null;
this.right = null;
}
}

public class PrintColumnOrder {

static void printInOrder(Node n) {
if (n == null)
return;
else {
printInOrder(n.left);
System.out.print(n.data + " ");
printInOrder(n.right);
}
}

static TreeMap cMap;

static void addColumn(Node n, int col) {
if (n == null)
return;
if (cMap.containsKey(col)) {
ArrayList<Integer> list = (ArrayList<Integer>) (cMap.get(col));
list.add(n.data);
} else {
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(n.data);
cMap.put(col, al);
}

addColumn(n.left, col - 1);
addColumn(n.right, col + 1);
}

static void pritColumnOrder(Node n) {
cMap = new TreeMap<Integer, List<Integer>>();
addColumn(n, 0);

Set<Map.Entry<Integer, ArrayList<Integer>>> s = cMap.entrySet();
for (Entry e : s) {
ArrayList<Integer> al = (ArrayList<Integer>) e.getValue();
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
System.out.println();
}

}

public static void main(String args[]) {

Node root = new Node(6);
root.left = new Node(3);
root.right = new Node(4);
root.left.left = new Node(5);
root.left.right = new Node(1);
root.left.left.left = new Node(9);
root.left.left.right = new Node(2);
root.left.left.right.right = new Node(7);
root.right.right = new Node(0);
root.right.right.left = new Node(8);
printInOrder(root);
System.out.println();
pritColumnOrder(root);
}
}
*/

- shailendra verma March 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <map>
#include <vector>
using namespace std;

map<int, vector<int> > mv;

class node{

public :

int data;
node* left;
node* right;
int index;

node(int data, node* left, node* right, int index){
  this->data = data;
  this->left = left;
  this->right = right;
  this->index = index;
}

};

node* insert(int data, node* n, int index){
  if(n == NULL){
     mv[index].push_back(data);
     n = new node(data, NULL, NULL, index);
  }else if(n->data > data){
     n->left = insert(data,n->left, index-1);
  }else if(n->data < data){
     n->right = insert(data, n->right, index+1);
  }

  return n;
}

void print_tree(node *n){
  if(n == NULL){
	return;
  }
  cout<<n->index<<" ";
  print_tree(n->left);
  print_tree(n->right);

}

int main()
{
  node* tree = NULL;
  int i = 0;
  tree = insert(6, tree, i);
  tree->left = insert(3, tree->left,i-1);
  tree->right = insert(4, tree->right,i+1);
  tree->right->right = insert(0, tree->right->right, i+2);
  tree->right->right->left = insert(8, tree->right->right->left, i+1);
  tree->left->left = insert(5, tree->left->left,i-2);
  tree->left->right = insert(1, tree->left->right,i);
  tree->left->left->left = insert(9, tree->left->left->left,i-3);
  tree->left->left->right = insert(2, tree->left->left->right,i-1);
  tree->left->left->right->right = insert(7, tree->left->left->right->right,i);

  for(map<int, vector<int> >::iterator it = mv.begin(); it!=mv.end();it++){
    for(int i=0;i<(*it).second.size();i++){
	cout<<(*it).second[i]<<" ";
    }
    //cout<<endl;
  }

  return 0;
}

- rhe29 March 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) time, O(N) space solution using BFS:

struct Node
    {
        int value;
        Node *left;
        Node *right;
    };

    void print_as_table(Node *const root)
    {
        struct Column
        {
            Column *prev;
            Column *next;
            std::vector<int> values;
        };  
        struct Pending
        {   
            Node *node;
            Column *column;
        };  
        std::deque<Pending> pendings;
        Column rootColumn = {nullptr, nullptr, {}};
        Column *leftColumn = &rootColumn;
        pendings.push_back({root, &rootColumn});
        while (!pendings.empty())
        {   
            const Pending pending = pendings.front();
            pendings.pop_front();
            Node *node = pending.node;
            if (node)
            {   
                Column *column = pending.column;
                column->values.push_back(node->value);
                if (node->left)
                {   
                    if (!column->prev)
                    {   
                        column->prev = new Column;
                        column->prev->prev = nullptr;
                        column->prev->next = column;
                        leftColumn = column->prev;
                    }   
                    pendings.push_back({node->left, column->prev});
                }
                if (node->right)
                {
                    if (!column->next)
                    {
                        column->next = new Column;
                        column->next->next = nullptr;
                        column->next->prev = column;
                    }
                    pendings.push_back({node->right, column->next});
                }
            }
        }
        for (Column *column = leftColumn; column; column = column->next)
        {
            for (const int v : column->values)
            {
                fprintf(stderr, "%i", v);
            }
        }
        fprintf(stderr, "\n");
    }

- wonder.mice March 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Key
{
public:
Key(int c, int d):column(c), depth(d){}
bool operator<(const Key& k) const
{
if(column == k.column)
return depth < k.depth;
return column < k.column;
}
public:
int column;
int depth;
};

class Solution {
public:
void printInColumn(TreeNode *T)
{
multimap<Key, int> m;
traverseTree(0, 0, T, m);
multimap<Key, int>::iterator iter = m.begin();
for(; iter != m.end(); iter++)
cout<<iter->second<<" ";
cout<<endl;

}
void traverseTree(int depth, int column, TreeNode *T, multimap<Key, int> &m)
{
if(T != NULL)
{
m.insert(make_pair(Key(column, depth), T->val));
traverseTree(depth+1, column-1, T->left, m);
traverseTree(depth+1, column+1, T->right, m);
}
}
};

- ylf951 March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume the binary tree node structure as follows:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Use pair<column, depth> as key in multimap.
Here column of a node is defined recursively as:
1) Column of root node is 0;
2) Column of left child of one's node equals its column - 1, column of right child equals its column + 1.
Depth of a node is defined recursively as:
1) For root node, depth is 0;
2) For other nodes, depth is their parent's depth + 1;

class Key
{
public:
    Key(int c, int d):column(c), depth(d){}
    bool operator<(const Key& k) const
    {
        if(column == k.column)
            return depth < k.depth;
        return column < k.column;
    }
public:
    int column;
    int depth;
};

//C++ solution
class Solution {
public:
    void printInColumn(TreeNode *T)
    {
        multimap<Key, int> m;
        traverseTree(0, 0, T, m);
        multimap<Key, int>::iterator iter = m.begin();
        for(; iter != m.end(); iter++)
            cout<<iter->second<<" ";
        cout<<endl;
        
    }
    void traverseTree(int column, int depth, TreeNode *T, multimap<Key, int> &m)
    {
        if(T != NULL)
        {
            m.insert(make_pair(Key(column, depth), T->val));
            traverseTree(column-1, depth+1, T->left, m);
            traverseTree(column+1, depth+1, T->right, m);
        }
    }
};

Space complexity: O(n)
Time complexity: O(n log (n))

- ylf951 March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my implementation - Turns out you can exploit some substructure in the problem to do it in O(n) without needing to use fancy radix/bucket sorts.

def print_tree_left_to_right_optim(tree_node):
    '''
    Print tree left to right, top to bottom
    '''
    from collections import defaultdict
    cache = defaultdict(list) # list for each horizontal row
    min_index, max_index = 0, 0

    def traverse_tree(node, depth=0, horizontal=0):
        nonlocal cache, min_index, max_index
        if node == None:
            return
        cache[horizontal] += [(depth, node.value)] 
        # O(1) - Ensures each hash is already sorted by depth
        min_index, max_index = min(min_index, horizontal), max(max_index, horizontal) 
        # Updating indices
        traverse_tree(node.left, depth+1, horizontal-1)
        traverse_tree(node.right, depth+1, horizontal+1)

    traverse_tree(tree_node)
    output = []
    # We can do this because we know indices are adjacent
    for i in range(min_index, max_index+1):
        output += cache[i] 
        # Appending an element to python list is amortized O(1)
    output = [str(o[-1]) for o in output] # Some O(n) processing
    print (" ".join(output)) # More O(n) processing
    return cache

- anjishnu.kr March 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looked at above proposed solutions. Break the problem into subproblems. Employ use of a stack. I beleive you can achieve performance in linear time. Its simple traverse through the right side first, push rightmost into a stack, then push the left tree and so on. Im sure the algo can be improved.

import java.util.Stack;

public class BTree {
    public static <T>  void pushRightSide(BNode<T> current,Stack<BNode<T>> stack){
        if(current.rightChild!=null) {
            pushRightSide(current.rightChild,stack);
        }
        if(current.state== State.UnVisited) {
            current.state = State.Visited;
            stack.push(current);
        }
        if(current.leftChild!=null) {
            pushRightSide(current.leftChild,stack);
        }
        if(current.leftChild!=null) {
            pushLeftSide(current.leftChild,stack);
        }

    }

    public static <T>  void pushLeftSide(BNode<T> current,Stack<BNode<T>> stack){

        if(current.rightChild!=null) {
            pushLeftSide(current.rightChild,stack);
        }

        if(current.state== State.UnVisited) {
            current.state = State.Visited;
            stack.push(current);
        }

        if(current.leftChild!=null) {
            pushRightSide(current.leftChild,stack);
        }

        if(current.leftChild!=null) {
            pushLeftSide(current.leftChild,stack);
        }
    }


    public static <T>  void printColumnarTree(BNode<T> current){

        Stack<BNode<T>> stack = new Stack<>();

        pushRightSide(current.rightChild,stack);
        stack.push(current);
        pushLeftSide(current.leftChild,stack);

        while(!stack.isEmpty()) {
            System.out.println( " " + stack.pop().val);
        }
    }



    public static void main(String ...args) {
        BNode<Integer> one = new BNode<>(1,null);
        BNode<Integer> two = new BNode<>(2,one);
        BNode<Integer> three = new BNode<>(3,one);

        BNode<Integer> four = new BNode<>(4,one);
        BNode<Integer> five = new BNode<>(5,one);

        BNode<Integer> seven = new BNode<>(7,three);
        BNode<Integer> eight = new BNode<>(8,three);

        BNode<Integer> eightyone = new BNode<>(81,eight);
        BNode<Integer> eightytwo = new BNode<>(82,eight);


        one.setLeftChild(two).setRightChild(three);
        two.setLeftChild(four).setRightChild(five);
        three.setLeftChild(seven).setRightChild(eight);
        eight.setLeftChild(eightyone).setRightChild(eightytwo);

        printColumnarTree(one);

    }


    public static class BNode<T> {

        T val;
        Graph.State state = Graph.State.UnVisited;
        BNode parent;
        BNode leftChild;
        BNode rightChild;

        public BNode(T val,BNode<T> parent) {
            this.val = val;
            this.parent = parent;
        }

        public BNode<T> setLeftChild(BNode leftChild) {
            this.leftChild = leftChild;
            return this;
        }

        public BNode<T> setRightChild(BNode rightChild) {
            this.rightChild = rightChild;
            return this;
        }
    }
}
public enum State{
        Visiting,Visited,UnVisited;
}

- raptor.flaps March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) space and time in C

Using column ID diff from root as the hash key. Root will be column 0, one on the left will be column-1 and for right it will be column+1. Using pre-order traversal to assign column ID to each element and then inserting the elements in the hash. Due to pre-order traversal the column ordering is maintained within the hash buckets.

#include <stdio.h>

ehash_t hash;
int min_column = 0;
int max_column = 0;

void compute_column(node_t* node, int current_column)
{
	if (current_column < min_column) {
		min_column = current_column;
	} else if (current_column > max_column) {
		max_column = current_column;
	}
	hash.insert(current_column, node->data);
	
	if (node->left != NULL) {
		compute_column(node->left, current_column - 1);
	}
	
	if (node->right != NULL) {
		compute_column(node->right, current_column + 1);
	}
}
void print_columns()
{
	for (int i = min_column; i < max_column; ++i)
	{
		hash.print(i);
	}
}

int main(int argc, char const *argv[])
{
	compute_column(root, 0);
	print_columns();
	return 0;
}

- killbot April 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public SortedDictionary<int, List<Node<T>>> dict = new SortedDictionary<int, List<Node<T>>>();
public void  VerticalTraverse(Node<T> node, int pos )
        {
            Queue<Tuple<int, Node<T>>> q = new Queue<Tuple<int, Node<T>>>();
            q.Enqueue(new Tuple<int, Node<T>>(0,node));
           
            while (q.Count > 0)
            {
                var n = q.Dequeue();

                if (!dict.ContainsKey(n.Item1))
                {
                    dict.Add(n.Item1, new List<Node<T>>());
                }
                dict[n.Item1].Add(n.Item2);
                if (n.Item2.Left != null) q.Enqueue(new Tuple<int, Node<T>>(n.Item1-1,n.Item2.Left));
                if (n.Item2.Right != null) q.Enqueue(new Tuple<int, Node<T>>(n.Item1 + 1, n.Item2.Right));
                           
            }

}

// Call it like this

btree.VerticalTraverse(btree.Root, 0);
            Debug.WriteLine("Vertical Traverse" + String.Join("->", btree.dict.Values.ToArray().SelectMany(p=>p).Select(p=>p.Data)));

- saisatish May 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity: O(n) --> Traverse tree two times: n + n
Space Complexity: O(n) --> recursive + columns : n + n

struct TreeNode{
	int val;
	TreeNode *right;
	TreeNode *left;
	TreeNode(int x): val(x), right(NULL), left(NULL){};
};


void getColumns(TreeNode *node, int & min, int &max , int cur){
	if(node == NULL ) return;
	if(cur < min) min = cur;
	if(cur > max) max = cur;
	getColumns(node->left, min, max, cur-1);
	getColumns(node->left, min, max, cur+1);
}

void fillColumn(TreeNode *node, int col, vector<vector<int> > & colums){
	if(node == NULL) return;
	colums[col].push_back(node->val);
	fillColumn(node->left, col-1, colums);
	fillColumn(node->right, col+1, colums);
}

void printColumns(TreeNode *root){
	int min= INT_MAX, max=INT_MIN;
	getColumns(root, min, max, 0);
	int numColumns = max - min + 1;
	vector<vector<int> > colums;
	vector<int> temp;
	for(int i =0 ; i < numColumns ; ++i){
		colums.push_back(temp);
	}
	fillColumn(root, -min, colums);
	for(auto & c : colums){
		for(auto & i : c)
			cout << i << ", ";
	}
	cout << endl;
}

- tanmay001 May 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple tree traversal then sort.
Time complexity: O(n log n), Space complexity: O(n).
code:

struct TreeNode{
    int val;
    TreeNode* left, *right;
    TreeNode(int x){
        val = x;
        left = right = NULL;
    }
};

struct output_node{
    int row, column;
    int val;
    output_node(int row, int column, int val){
        this->row = row;
        this->column = column;
        this->val = val;
    }
    
};

void traverse_tree(TreeNode* node, int row, int column, vector<output_node*> &nodes){
    if(node == NULL){
        return;
    }
    nodes.push_back(new output_node(row, column, node->val));
    
    traverse_tree(node->left, row+1, column-1, nodes);
    traverse_tree(node->right, row+1, column+1, nodes);
    
}
bool compare(output_node *a, output_node *b){
    if(a->column < b->column)
        return true;
    else if(a->column > b->column)
        return false;
    return a->row < b->row;
}
void print_inColumn_order(TreeNode* root){
    if(root == NULL){
        return;
    }
    vector<output_node*> nodes;
    traverse_tree(root, 0, 0, nodes);
    sort(nodes.begin(), nodes.end(), compare);
    printf("%d", nodes[0]->val);
    for(int i=1; i<nodes.size(); i++){
        printf(" %d", nodes[i]->val);
    }
    printf("\n");
}

- mirak94 September 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_moves(head):
    columns = {}
    print(head)
    def moves_to_node(node, column):
        print("Node: {}, Column: {}".format(node, column))
        if columns.get(column):
            columns[column].append(node.data)
        else:
            columns[column] = [node.data]
        if node.left:
            moves_to_node(node.left,column-1)
        if node.right:
            moves_to_node(node.right, column + 1)

    moves_to_node(head, 0)
    return columns

def sort_print_columns(columns):
    order = sorted(columns)
    for i in order:
        columns[i]
        for n in columns[i]:
            print(n)

class Node:
    def __init__(self, data, left=None, right=None):
        self.left = left
        self.right = right
        self.data = data

a = Node(7)
b = Node(8)
c = Node(3, a, b)
d = Node(4)
e = Node(6, c, d)

sort_print_columns(get_moves(e))

- sloan@glympse.com September 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.sample;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class ColumnWiseTreePrint {

private static Map<Integer,ArrayList<Integer>> map = new TreeMap<>();

private static class TreeNode{
TreeNode left;
TreeNode right;
int data;

public TreeNode(TreeNode left, TreeNode right, int data){
this.left = left;
this.right = right;
this.data = data;
}
}
private static void columns(TreeNode a, int column){

if(a==null){
return;
}
if(map.containsKey(column)){
ArrayList<Integer> list = map.get(column);
list.add(a.data);
}
else{
ArrayList<Integer> list = new ArrayList<>();
list.add(a.data);
map.put(column, list);
}
columns(a.left,column-1);
columns(a.right,column+1);


}
public static void main(String[] args) {
// TODO Auto-generated method stub

TreeNode n9 = new TreeNode(null,null,9);
TreeNode n7 = new TreeNode(null,null,7);
TreeNode n1 = new TreeNode(null,null,1);
TreeNode n8 = new TreeNode(null,null,8);

TreeNode n2 = new TreeNode(null,n7,2);
TreeNode n5 = new TreeNode(n9,n2,5);
TreeNode n3 = new TreeNode(n5,n1,3);

TreeNode n0 = new TreeNode(n8,null,0);
TreeNode n4 = new TreeNode(null,n0,4);

TreeNode n6 = new TreeNode(n3,n4,6);

columns(n6, 0);

Set<Integer> set = map.keySet();

Iterator<Integer> it = set.iterator();

while(it.hasNext()){
int columns = it.next();
List<Integer> list = map.get(columns);
for(int item : list){
System.out.print(item + " ");
}
}

}

}

- Mohit September 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//O(nlogn), while loop for each level of the tree, for loop for each node at that level.

/**
	 * Returns the vertical traversal of a tree. Uses a wrapper around TreeNode to store current index.
	 * Root is at 0. 6 and 10 are also at 0. 5 is at -1, 3 is at -2 etc.
	 * 			8
	 * 		5		12
	 *   3	  6  10	   11
	 */
	public static Map<Integer, List<TreeNodeWrapper>> getVerticalList(TreeNode root) {
    	LinkedList<TreeNodeWrapper> current = new LinkedList<TreeNodeWrapper>();
    	Map<Integer, List<TreeNodeWrapper>> indexMap = new HashMap<Integer, List<TreeNodeWrapper>>();
    	int index = 0;
    	if(root != null) {
    		current.add(new TreeNodeWrapper(index, root));    		
    		indexMap.put(index, current);
    	}
    	while(current.size() > 0) {
    		// parents become current, current move to next level
    		LinkedList<TreeNodeWrapper> parents = current;
    		current = new LinkedList<TreeNodeWrapper>();
    		
    		for(final TreeNodeWrapper n: parents) {
    			// visit each child
    			if(n.node.left != null) {
    				int i = n.currentIndex - 1;
    				TreeNodeWrapper child = new TreeNodeWrapper(i, n.node.left); 
    				current.add(child);
    				List<TreeNodeWrapper> temp = indexMap.get(i);
    				if(temp == null)
    					temp = new ArrayList<TreeNodeWrapper>();
    				temp.add(child);
    				indexMap.put(i, temp);
    			}
    			if(n.node.right != null) {
    				int i = n.currentIndex + 1;    
    				TreeNodeWrapper child = new TreeNodeWrapper(i, n.node.right);
    				current.add(child);
    				List<TreeNodeWrapper> temp = indexMap.get(i);
    				if(temp == null)
    					temp = new ArrayList<TreeNodeWrapper>();
    				temp.add(child);
    				indexMap.put(i, temp);
    			}
    		}
    	}   	
    	return indexMap;
    }

// Typical TreeNode of a BST

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(final int _data) {
        this.data = _data;
    }
}

// TreeNodeWrapper

class TreeNodeWrapper {
	int currentIndex;
	TreeNode node;
	TreeNodeWrapper(int index, TreeNode node) {
		this.currentIndex = index;
		this.node = node;
	}
}

- code.runner October 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// ZoomBA
mapping = dict()
// the basic mapping is created using this 
def traverse( node , cur_x, cur_y ){
  if ( !(cur_x @ mapping) ){  mapping[cur_x] = list() }
  // append :store both y co ordinate as well as value
  mapping[cur_x].add ( [ cur_y , node.value ])  
  // change the x to left, so one minus, and level one down 
  if ( !empty( node.left) ) { traverse( node.left, cur_x - 1, cur_y + 1 ) }
  // change the x to right, so one plus, and level one down
  if ( !empty( node.right) ) { traverse( node.right, cur_x + 1, cur_y + 1 ) }
}
traverse( root, 0, 0 ) // basis 
// sort the keys based on x coordinate 
keys = sorta ( list ( mapping.keySet ) )
fold ( keys ) ->{
   values = mapping[$.item] // get the pair values in that key 
   // sort the values based on the pairs left item, e.g. y coordinate
   sorta( values ) :: { $.item[0][0] < $.item[1][0]  }
   // now, simply print all the values : the right value 
   printf ( '%s', str( values , ' ') ->{  $.item[1] } )
}
// end with a newline 
println()

- NoOne October 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Almost O(n). At least can be easily improved to O(n) by using deque instead of queue.

#import <Foundation/Foundation.h>

@interface Queue : NSObject

@property ( nonatomic, readonly) NSMutableArray* array;

- (void) push:(id) obj;
- (id) pop;
- (bool) isEmpty;
@end


@implementation Queue

- (instancetype)init
{
    self = [super init];
    if (self) {
        _array = [NSMutableArray new];
    }
    return self;
}

- (void) push:(id) obj{
    [self.array addObject:obj];
}
- (id) pop{
    id obj = self.array[0];
    [self.array removeObjectAtIndex:0];
    return obj;
}
- (bool) isEmpty{
    return self.array.count == 0;
}


@end

@interface TreeNode : NSObject

@property (nonatomic, strong) TreeNode* left;
@property (nonatomic, strong) TreeNode* right;
@property (nonatomic, assign) int value;

@end

@interface QueueNode : NSObject

@property (nonatomic, strong) TreeNode* node;
@property (nonatomic, assign) int pos;

- (instancetype)initWithNode:(TreeNode*) node pos:(int) pos;
@end


@interface ListNode : NSObject

@property (nonatomic, strong) ListNode* next;
@property (nonatomic, assign) int value;

@end

@implementation QueueNode

- (instancetype)initWithNode:(TreeNode*) node pos:(int) pos
{
    self = [super init];
    if (self) {
        _node = node;
        _pos = pos;
    }
    return self;
}

@end

@implementation ListNode

@end

@implementation TreeNode


@end


int calcNodes(TreeNode* node){
    int sum = 1;
    if(node.left){
        sum+= calcNodes(node.left);
    }
    if(node.right){
        sum+= calcNodes(node.right);
    }
    return sum;
}

void addNodeToPlainStructure(TreeNode* node, NSMutableArray* plain, int pos){
    ListNode* listNode = [ListNode new];
    listNode.value = node.value;
    
    if([plain[pos] isKindOfClass:[NSNull class]]){
        plain[pos] = listNode;
    }else{
        ListNode* prevNode = plain[pos];
        while(prevNode.next){
            prevNode = prevNode.next;
        }
        prevNode.next = listNode;
    }
}
                             

void addTreeToPlainStructure(TreeNode* rootNode, NSMutableArray* plain, int pos){
    Queue* queue = [Queue new];
    [queue push:[[QueueNode alloc] initWithNode:rootNode pos:pos]];
    while(![queue isEmpty]){
        QueueNode* node = [queue pop];
        if(node.node.left){
            [queue push:[[QueueNode alloc] initWithNode:node.node.left pos:node.pos -1]];
        }
        if(node.node.right){
            [queue push:[[QueueNode alloc] initWithNode:node.node.right pos:node.pos +1]];
        }
        addNodeToPlainStructure(node.node, plain, node.pos);
    }
}


NSArray* createPlainStructure(TreeNode* node, int count){
    NSMutableArray* plain = [NSMutableArray new];
    for(int i = 0; i < count; i++){
        [plain addObject:[NSNull null]];
    }
    addTreeToPlainStructure(node, plain, count/2);
    return plain;
}

void outputMap(NSArray* map){
    for(int i = 0; i < map.count; i++){
        if ([map[i] isKindOfClass:[NSNull class]]) {
            continue;
        }
        ListNode* node = map[i];
        while(node){
            printf("%d", node.value);
            node = node.next;
        }
    }
}
TreeNode* generateTestData1(){
    TreeNode* node1 = [TreeNode new];
    node1.value = 1;
    TreeNode* node2 = [TreeNode new];
    node2.value = 2;
    TreeNode* node3 = [TreeNode new];
    node3.value = 3;
    TreeNode* node4 = [TreeNode new];
    node4.value = 4;
    TreeNode* node5 = [TreeNode new];
    node5.value = 5;
    TreeNode* node6 = [TreeNode new];
    node6.value = 6;
    TreeNode* node7 = [TreeNode new];
    node7.value = 7;
    
    node1.left = node2;
    node1.right = node3;
    
    node2.left = node4;
    node2.right = node5;
    
    node3.left = node6;
    node3.right = node7;
    
    return node1;
}

int main(int argc, const char * argv[]){
    TreeNode* root = generateTestData();
    
    int n = calcNodes(root);
    NSArray* map = createPlainStructure(root, n*2);
    outputMap(map);
    
    return 0;
}

- Krizai November 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple level order traversal:

import java.util.*;

public class Columns_of_Binary_Tree_5749533368647680{
  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,
            new Node(6,null,null),
            new Node(7,null,null)
          )
        );
    Column mid = new Column();
    mid.nodes.add(root);
    Deque<Column> deq = new ArrayDeque<>();
    deq.addLast(mid);
    while(!deq.isEmpty()){
      Column col = deq.removeFirst();
      Node node = col.nodes.get(col.nodes.size()-1);
      if (node.l != null){
        col.l = col.l == null ? new Column() : col.l;
        col.l.r = col;
        col.l.nodes.add(node.l);
        deq.addLast(col.l);
      }
      if (node.r != null){
        col.r = col.r == null ? new Column() : col.r;
        col.r.l = col;
        col.r.nodes.add(node.r);
        deq.addLast(col.r);
      }
    }

    Column col = mid;
    while(col.l != null){
      col = col.l;
    }
    while(col != null){
      System.out.print("|");
      col.printNodes();
      col = col.r;
    }
    System.out.println();
  }
}
class Column{
  LinkedList<Node> nodes = new LinkedList<>();
  Column l, r;
  Node node;

  void printNodes(){
    for(Node node : nodes){
      System.out.print(node.val);
      System.out.print(" ");
    }
  }
}
class Node{
  int val;
  Node l, r;
  Node(int val, Node l, Node r){
    this.val = val;
    this.l = l;
    this.r = r;
  }
}

- Anonymous December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class Columns_of_Binary_Tree_5749533368647680{
  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,
            new Node(6,null,null),
            new Node(7,null,null)
          )
        );
    Column mid = new Column();
    mid.nodes.add(root);
    Deque<Column> deq = new ArrayDeque<>();
    deq.addLast(mid);
    while(!deq.isEmpty()){
      Column col = deq.removeFirst();
      Node node = col.nodes.get(col.nodes.size()-1);
      if (node.l != null){
        col.l = col.l == null ? new Column() : col.l;
        col.l.r = col;
        col.l.nodes.add(node.l);
        deq.addLast(col.l);
      }
      if (node.r != null){
        col.r = col.r == null ? new Column() : col.r;
        col.r.l = col;
        col.r.nodes.add(node.r);
        deq.addLast(col.r);
      }
    }

    Column col = mid;
    while(col.l != null){
      col = col.l;
    }
    while(col != null){
      System.out.print("|");
      col.printNodes();
      col = col.r;
    }
    System.out.println();
  }
}
class Column{
  LinkedList<Node> nodes = new LinkedList<>();
  Column l, r;

  void printNodes(){
    for(Node node : nodes){
      System.out.print(node.val);
      System.out.print(" ");
    }
  }
}
class Node{
  int val;
  Node l, r;
  Node(int val, Node l, Node r){
    this.val = val;
    this.l = l;
    this.r = r;
  }
}

- madno December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Do any traversal to figure out the width of the tree (root is 0, anything to the left is negative, anything to the right is positive).
2. Create a linked HashMap of integers to trees and for key in range (left of tree to right of tree) insert an empty linked list.
3. Do any traversal to add nodes to the linked list relative to their position from the root.
4. Print all the linked-lists in the linkedHashMap in order.

- desirocker125 August 14, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More