Facebook Interview Question
Software DevelopersCountry: 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
*/
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)
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);
}
}
}
- gera October 27, 2018