Facebook Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
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);
}
}
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);
}
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.
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");
}
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!
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 + " ");
}
}
}
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);
}
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)
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";
}
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);
}
}
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
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);
}
}
}
}
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);
}
}
/*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);
}
}
*/
#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;
}
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");
}
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);
}
}
};
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))
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
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;
}
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;
}
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)));
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;
}
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))
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 + " ");
}
}
}
}
//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;
}
}
// 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()
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;
}
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;
}
}
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;
}
}
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.
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).
- naren February 26, 2016public 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); } }