Facebook Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
Does this work correctly? It looks like this is essentially doing a DFS traversal so it could improperly add node depth-wise. Imagine if in the example in the OP there was a child node to the right of the node with value 0, let's say with value 8. The printout should then be 5 9 0 6 1 8 4 7 3, but this function will output 5 9 0 6 8 1 4 7 3. I think you need to do BFS with a queue.
static void print(Node n) {
Deque<Node> stack = new ArrayDeque<>();
while (n != null) {
stack.push(n);
n = n.l;
}
doStack(stack);
}
static void doStack(Deque<Node> stack) {
if (stack.isEmpty()) {return;}
Node prev = stack.pop();
System.out.println(prev.v);
while (!stack.isEmpty()) {
Node n = stack.pop();
System.out.println(n.v);
print(prev.r);
prev = n;
}
print(prev.r);
}
Clever but supports only tree example in question. It doesn't support tree like this:
*
* ..............6
* ............/...\
* ...........9.....4
* ........../..\....\
* .........5....1....6
* ..........\......../
* ...........0.... .7
* .............\.......
* ..............11
* ................\
* .................12
* ...................\
* ...................13
* .....................\
* ......................14
*/
Algorithm:
- Do a inorder tree traversal with following changes
Root Node is denoted with Row Ordinal and Column Ordinal as 0
Every time traversal take a left, Column Ordinal is decremented by 1
Every time traversal take a right, Column Ordinal is incremented by 1
Every time traversal takes to children, Row Ordinal is incremented by 1
Every time traversal moves back to parent, Row Ordinal is decremented by 1
- Sort Nodes based on Column Ordinal, if Column Ordinal matches, then use Row Ordinal
- Print Sorted Nodes
Psuedo-Code:
- Class Node definition is (Value, Left, Right)
- Class NodeEx definition is (Value, RowOrdinal, ColumnOrdinal)
class TreePrinter {
private Node treeRootNode;
private ArrayList<NodeEx> nodes;
public TreePrinter(Node rootNode) {
this.treeRootNode = rootNode;
this.nodes = new ArrayList<NodeEx>();
}
public void printTree() {
this.nodes.clear();
traverseInOrder(rootNode, 0, 0);
sortNodesByOrdinals();
printNodes();
}
private void traverseInOrder(Node node, int rowOrdinal, int columnOrdinal) {
if (null == node) return;
this.nodes.append(new NodeEx(node.value, rowOrdinal, columnOrdinal));
traverseInOrder(node.Left, rowOrdinal+1, columnOrdinal-1);
traverseInOrder(node.Right, rowOrdinal+1, columnOrdinal+1);
}
private sortNodesByOrdinals() {
nodes.sort_by(node1, node2) {
if node1.ColumnOrdinal < node2.ColumnOrdinal return -1;
else node1.ColumnOrdinal > node2.ColumnOrdinal return +1;
else if node1.RowOrdinal < node2.RowOrdinal return -1;
else if node1.RowOrdinal > node2.RowOrdinal return +1;
else return 0;
}
}
}
public class ByColumnTree {
public static void main(String[] args) {
Node root = root(6);
Node n9 = root.left(9);
n9.left(5).right(0);
n9.right(1);
root.right(4).right(3).left(7);
List<Node> fringe = new LinkedList<>();
traverse(fringe, root);
Collections.sort(fringe);
System.out.println(fringe);
}
private static void traverse(List<Node> fringe, Node node) {
fringe.add(node);
if(node.left != null) traverse(fringe, node.left);
if(node.right != null) traverse(fringe, node.right);
}
static class Node implements Comparable<Node> {
Node left;
Node right;
int val;
int displacement;
int depth;
Node parent;
static Node root(int val) {
var node = new Node();
node.val = val;
return node;
}
Node left(int val) {
var node = new Node();
node.val = val;
node.depth = this.depth + 1;
node.displacement = this.displacement + 1;
node.parent = this;
this.left = node;
return node;
}
Node right(int val) {
var node = new Node();
node.val = val;
node.depth = this.depth + 1;
node.displacement = this.displacement - 1;
node.parent = this;
this.right = node;
return node;
}
@Override
public int compareTo(Node other) {
int d = Integer.compare(other.displacement, this.displacement);
if (d != 0) return d;
return Integer.compare(this.depth, other.depth);
}
@Override
public String toString() {
return String.valueOf(val);
}
}
}
class Node:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
def getcoldistance(root,horzdist,mydict):
if not root:
return None
if horzdist in mydict:
mydict[horzdist].append(root.val)
else:
mydict[horzdist] = [root.val]
getcoldistance(root.left,horzdist-1,mydict)
getcoldistance(root.right,horzdist+1,mydict)
def printvertdist(root):
m = {}
getcoldistance(root,0,m)
for key in sorted(m):
for val in m[key]:
print(val,end='')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)
printvertdist(root)
using level order traversal and keeping a hash map to preserve the order
void printTree(TreeNode root){
Queue<Pair> q = new LinkedList<Pair>();
TreeMap<Integer,LinkedList<Integer>> map = new TreeMap<Integer,LinkedList<TreeNode>> ();
if(root==null){
return;
}
q.add(new Pair(root,0));
int hd =0;
addValue(map, 0, root.val)
while(q.size()>0){
Pair pair = (Pair)q.poll();
TreeNode temp = q.getTreeNode();
hd = q.getHd();
if(temp.left!=null){
q.add(new Pair(temp.left,hd-1));
addValue(map, hd-1, temp.val);
}
if(temp.right!=null){
q.add(new Pair(temp.right,hd+1));
addValue(map, hd+1, temp.val);
}
}
Iterator<Integer> itr = map.getKeySet();
while(itr.hasNext()){
int key = (Integer)itr.next();
LinkedList l = map.get(key);
while(l!=null){
System.out.print(l.val+" ");
l= l.next;
}
}
}
void addValue(map, int key, int val){
if(map.get(key)==null){
LinkedList<Integer> l = new LinkedList<Integer>();
l.add(root.val);
map.put(0,l);
} else{
LinkedList<Integer> l = (LinkedList<Integer>)map.get(key);
l.add(val);
}
}
class Pair {
TreeNode node;
int hd;
public Pair(TreeNode node,int hd){
this.node = node;
this.hd =hd;
}
}
Traverse Breadth-First to preserve order for nodes with the same horizontal distance. Horizontal distance is used to find nodes in the same column I.e. horizontal distance for nodes 4, 7 and 12 is 1.
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/
private void printInVerticalOrder(Node root) {
if (root == null){
return;
}
TreeMap<Integer, List<Integer>> hdToValues = collectHorizontalDistancesToValues(root);
print(hdToValues);
}
private TreeMap<Integer, List<Integer>> collectHorizontalDistancesToValues(Node root) {
TreeMap<Integer, List<Integer>> hdToValues = new TreeMap<>();
LinkedList<HDNode> nodes = new LinkedList<>();
nodes.add(new HDNode(0, root));
while (!nodes.isEmpty()) {
HDNode hdNode = nodes.removeFirst();
hdToValues.putIfAbsent(hdNode.hd, new ArrayList<>());
hdToValues.get(hdNode.hd).add(hdNode.node.value);
if(hdNode.node.left != null){
nodes.add(new HDNode(hdNode.hd - 1, hdNode.node.left));
}
if(hdNode.node.right != null){
nodes.add(new HDNode(hdNode.hd + 1, hdNode.node.right));
}
}
return hdToValues;
}
private void print(TreeMap<Integer, List<Integer>> hdToValues) {
while (!hdToValues.isEmpty()) {
Map.Entry<Integer, List<Integer>> entry = hdToValues.pollFirstEntry();
entry.getValue().forEach(v -> System.out.print(v + " "));
System.out.println("\n");
}
}
private class HDNode {
int hd;
Node node;
HDNode(int hd, Node node) {
this.hd = hd;
this.node = node;
}
}
Class Data {
public int nodeVal;
public int dist;
public Data(int n, int d) { nodeVal = n; dist = d;}
}
void stupidTreePrint(Node root) {
List<Data> arr = new ArrayList<>();
auxFunc(root, 0, arr);
// stable sort
Collection.sort(arr, (o1, o2) -> Integer.signum(o1.dist-o2.dist));
arr.foreach(e -> System.out.println(" " + e.nodeval + " "));
}
void auxFunc(Node root, int dist, List<Data> arr) {
if(root == null) return;
Data tmp = new Data(root.value, dist);
arr.add(tmp);
auxFunc(root.left, dist - 1, arr);
auxFunc(root.right, dist + 1, arr);
}
python implementation
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/
class Node:
def __init__(self, val:int, left=None, right=None):
self.val,self.left,self.right = val,left,right
def __repr__(self): return f'{self.val}'
def mark_nodes(root, index, depth, res):
cut = None
if root.left is not None:
mark_nodes(root.left, index-1, depth+1, res)
res.append((root, index, depth))
if root.right is not None:
mark_nodes(root.right, index+1, depth+1, res)
def print_lrtd(sorted_nodes):
accum = []
mark_nodes(root, 0, 0, accum)
sorted_nodes = sorted(accum, key=lambda x: (x[1],x[2]))
return [i[0] for i in sorted_nodes]
Output:
stem = Node(0, None, Node(11, None, Node(12, None, Node(13, None, Node(14)))))
root = Node(6, Node(9, Node(5, None, stem), Node(1)), Node(4, None, Node(3, Node(7))))
print_lrtd(root)
def Node : { val : null, left : null, right : null }
def Entry : { node : null, x : null, y : null }
def make_entries( entry_list, root , x_pos, y_pos ){
entry_list += new ( Entry, root, x_pos, y_pos )
if ( !empty( root.left ) ) { make_entries( entry_list, root.left, x_pos - 1, y_pos + 1 ) }
if ( !empty( root.right ) ) { make_entries( entry_list, root.right, x_pos + 1, y_pos + 1 ) }
}
def visit_tree_column_and_row_wise( root ){
entries = make_entries( list(), root, 0, 0 )
// sort all entries by x_pos and then y_pos
sorta( entry_list ) where {
left_entry = $.l
right_entry = $.r
prec = sign( left_entry.x - right_entry.x )
if ( prec !=0 ) return prec
sign( left_entry.y - right_entry.y )
}
println( str( entry_list , "," ) as { $.node.val } )
}
class TNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def to_indexed_list(tree, row, col, nodes):
nodes.append(((col, row), tree.value))
if tree.left:
to_indexed_list(tree.left, row + 1, col - 1, nodes)
if tree.right:
to_indexed_list(tree.right, row + 1, col + 1, nodes)
def print_tree(t):
nodes = []
to_indexed_list(t, 0, 0, nodes)
nodes = sorted(nodes, key=lambda x: x[0])
for ((_, _), v) in nodes:
print(v)
t = TNode(6, TNode(9, TNode(5, None, TNode(0)), TNode(1)), TNode(4, None, TNode(3, TNode(7))))
print_tree(t)
int getTreeSize(node* root) {
if (root == NULL) {
return 0;
}
return 1 + getTreeSize(root->left) + getTreeSize(root->right);
}
void printColumnRowWise(node* root) {
int size = getTreeSize(root);
vector<int> cols[size];
// do a level order traversal
queue< pair<node*, int> > q;
q.push(make_pair(root, 0));
while (!q.empty()) {
// get the front node
pair<node*, int> p = q.front();
node* curr = p.first;
int curr_col = p.second;
// add the front node to cols vector
cols[curr_col + size / 2].push_back(curr->val);
if (curr->left) {
q.push(make_pair(curr->left, curr_col - 1));
}
if (curr->right) {
q.push(make_pair(curr->right, curr_col + 1));
}
// pop the front element
q.pop();
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < cols[i].size(); j++) {
cout << cols[i][j] << " ";
}
}
cout<<endl;
}
int getTreeSize(node* root) {
if (root == NULL) {
return 0;
}
return 1 + getTreeSize(root->left) + getTreeSize(root->right);
}
void printColumnRowWise(node* root) {
int size = getTreeSize(root);
vector<int> cols[size];
// do a level order traversal
queue< pair<node*, int> > q;
q.push(make_pair(root, 0));
while (!q.empty()) {
// get the front node
pair<node*, int> p = q.front();
node* curr = p.first;
int curr_col = p.second;
// add the front node to cols vector
cols[curr_col + size / 2].push_back(curr->val);
if (curr->left) {
q.push(make_pair(curr->left, curr_col - 1));
}
if (curr->right) {
q.push(make_pair(curr->right, curr_col + 1));
}
// pop the front element
q.pop();
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < cols[i].size(); j++) {
cout << cols[i][j] << " ";
}
}
cout<<endl;
}
int getTreeSize(node* root) {
if (root == NULL) {
return 0;
}
return 1 + getTreeSize(root->left) + getTreeSize(root->right);
}
void printColumnRowWise(node* root) {
int size = getTreeSize(root);
vector<int> cols[size];
// do a level order traversal
queue< pair<node*, int> > q;
q.push(make_pair(root, 0));
while (!q.empty()) {
// get the front node
pair<node*, int> p = q.front();
node* curr = p.first;
int curr_col = p.second;
// add the front node to cols vector
cols[curr_col + size / 2].push_back(curr->val);
if (curr->left) {
q.push(make_pair(curr->left, curr_col - 1));
}
if (curr->right) {
q.push(make_pair(curr->right, curr_col + 1));
}
// pop the front element
q.pop();
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < cols[i].size(); j++) {
cout << cols[i][j] << " ";
}
}
cout<<endl;
}
#include <iostream>
#include <map>
#include <deque>
using namespace std;
struct Node
{
int data;
struct Node* left{nullptr};
struct Node* right{nullptr};
Node(int i) : data(i) {}
};
map<int, deque<int>> sMaps{};
int sLevel;
void foo(Node* pRoot)
{
if (!pRoot)
{
return;
}
sMaps[sLevel].push_front(pRoot->data);
--sLevel;
foo(pRoot->left);
++sLevel;
++sLevel;
foo(pRoot->right);
--sLevel;
}
int main()
{
Node* pRoot = new Node(6);
pRoot->left = new Node(9);
pRoot->left->left = new Node(5);
pRoot->left->left->right = new Node(0);
pRoot->left->left->right->left = new Node(2);
pRoot->left->left->right->left->right = new Node(3);
pRoot->right = new Node(10);
pRoot->right->left = new Node(11);
pRoot->right->right = new Node(12);
foo(pRoot);
for (auto const& pair : sMaps)
{
auto const& deque = pair.second;
auto it = deque.crbegin();
auto end = deque.crend();
while (it != end)
{
cout << *it << '\n';
++it;
}
}
return 0;
}
/*
5
2
9
0
3
6
11
10
12
*/
void print_tree(tree t) {
int d = depth(t);
int level = 2;
int indent = (std::pow(2, d) * 5) / 2 + 1;
std::vector<std::pair<int, tree>> frontier = { {indent, t} };
std::vector<std::pair<int, tree>> new_frontier;
std::vector<std::pair<int, tree>>& curr_frontier = frontier;
std::vector<std::pair<int, tree>>& next_frontier = new_frontier;
while (!curr_frontier.empty()) {
int curr_indent = 0;
for (auto& pair : curr_frontier) {
print_indent(pair.first - curr_indent);
std::cout << pair.second->value;
curr_indent = pair.first;
}
std::cout << std::endl;
curr_indent = 0;
for (auto& pair : curr_frontier) {
if (pair.second->left != nullptr) {
print_indent(pair.first - (d - level + 1) - curr_indent);
std::cout << "/";
next_frontier.push_back({ pair.first - 2 * (d - level + 1), pair.second->left });
curr_indent = pair.first - (d - level + 1);
}
if (pair.second->right != nullptr) {
print_indent(pair.first + (d - level + 1) - curr_indent);
std::cout << "\\";
next_frontier.push_back({ pair.first + 2 * (d - level + 1), pair.second->right });
curr_indent = pair.first + (d - level + 1);
}
}
std::cout << std::endl;
curr_frontier.clear();
std::swap(curr_frontier, next_frontier);
++level;
}
}
- gera October 27, 2018// Utility function to store vertical order in map 'm' // 'hd' is horizontal distance of current node from root. // 'hd' is initially passed as 0 static void getVerticalOrder(Node root, int hd, TreeMap<Integer,Vector<Integer>> m) { // Base case if(root == null) return; //get the vector list at 'hd' Vector<Integer> get = m.get(hd); // Store current node in map 'm' if(get == null) { get = new Vector<>(); get.add(root.key); } else get.add(root.key); m.put(hd, get); // Store nodes in left subtree getVerticalOrder(root.left, hd-1, m); // Store nodes in right subtree getVerticalOrder(root.right, hd+1, m); } // The main function to print vertical oder of a binary tree // with given root static void printVerticalOrder(Node root) { // Create a map and store vertical oder in map using // function getVerticalOrder() TreeMap<Integer,Vector<Integer>> m = new TreeMap<>(); int hd =0; getVerticalOrder(root,hd,m); // Traverse the map and print nodes at every horigontal // distance (hd) for (Entry<Integer, Vector<Integer>> entry : m.entrySet()) { System.out.println(entry.getValue()); } }