Facebook Interview Question Software Engineer Interns
Country: United States
Interview Type: In-Person
I think the tricky part would be to print it with numbers
import math
def print_bst(depth):
bst = []
series = [i for i in range(depth+1)]
calc_spaces = lambda x: int(math.pow(2, x)) - 1
spaces = map(calc_spaces, series)
current_depth = depth
while current_depth > 0:
elements = ["*" for i in range( int(math.pow(2, current_depth)) , int(math.pow(2, current_depth+1)))]
bst.append(elements)
current_depth -= 1
bst.append(["*"])
bst.reverse()
result = []
current_depth = depth
while current_depth > 0:
line = " " * spaces[depth - current_depth]
for current_element in bst[current_depth]:
line += str(current_element) + " " * spaces[depth - current_depth + 1]
result.append(line)
current_depth -= 1
result.reverse()
print " " * spaces[depth] + "*"
for line in result:
print line
if __name__ == "__main__":
print_bst(6)
yep I stumble into the printing the numbers how is that going to offset the tree printing.
I solved it using a "matrix" populating List<List<Node>>
It took me wayyy more than half an hour. :-(
python
import sys
VERTEX = '*'
SPACE = ' '
MAX_LENGTH = 100
def print_bst(depth):
for i in xrange(depth):
vertex_count = 2**i
space_count = 2**(depth - i)
# pattern = SPACE * (space_count / 2 - 1) + VERTEX + SPACE * (space_count / 2)
# OR using python string.center() function
pattern = VERTEX.center(space_count, SPACE)
s = pattern * vertex_count
print s[:MAX_LENGTH - 1] + '|'
if __name__ == "__main__":
print_bst(int(sys.argv[1]))
Usage python test.py [depth]
As above the tricky part is how the numbers offset the tree printing I did a minor fix adding the length of the node.data.ToString() as part of how many spaces will leave before printing the parent.
static void PrintBinaryTree(Node root)
{
List<List<Node>> matrix = new List<List<Node>>();
TraverseTree(
0, /* Level */
matrix,
root);
PrintMatrix(matrix);
}
static int TraverseTree(int level, List<List<Node>> matrix, Node root)
{
if(root == null)
{
return 0;
}
int leftSpace = TraverseTree(level + 1, matrix, root.left);
int rightSpace = TraverseTree(level + 1, matrix, root.right);
AddNodeToMatrix(matrix, level, root, leftSpace, rightSpace + 1);
return leftSpace + node.data.ToString().Length + rightSpace + 1;
}
static void AddNodeToMatrix(
List<List<Node>> matrix,
int level,
Node root,
int leftSpace,
int rigthSpace)
{
while(matrix.Length < level)
matrix.Add(new List<Node>());
while(leftSpace > 0)
{
matrix[level].Add(null);
leftSpace--;
}
matrix[level].Add(node);
while(rightSpace > 0)
{
matrix[level].Add(null);
rightSpace--;
}
}
PrintMatrix(List<List<Node>> matrix)
{
foreach(List<Node> line in matrix)
{
foreach(Node node in line)
{
if(node == null)
{
Console.Write(" ");
}
else
{
Console.Write(node.data);
}
}
Console.WriteLine();
}
}
Here is a (not very efficient) algorithm that prints in levels. Complexity = O (n * ln n)
public static class Node {
Node left;
Node right;
int val;
public Node(int val) {
this.val = val;
}
// helper to get height
public int getHeight() {
int lheight = left != null ? left.getHeight() : 0;
int rheight = right != null ? right.getHeight() : 0;
return 1 + Math.max(lheight, rheight);
}
}
static void printTree(Node n) {
// get height, so we know how many rows to print and spaces for each level
int height = n.getHeight();
// print tree in levels, from level 0 ... height
for(int i = 0; i <= height; i++) {
// 3 << (height-1) is total number of spaces we use for one entry at height 'i'
printTree(n, i, 3 << (height-i));
System.out.println();
}
}
static void printTree(Node n, int heightToPrint, int spaces) {
if(heightToPrint == 0) {
print("" + n.val, spaces);
}
else {
if(n.left != null) printTree(n.left, heightToPrint-1, spaces);
else print("", spaces << (heightToPrint-1)); // fill with spaces
if(n.right != null) printTree(n.right, heightToPrint-1, spaces);
else print("", spaces << (heightToPrint-1)); // fill with spaces
}
}
static void print(String text, int desiredLength) {
int spaces = desiredLength - text.length();
int lspaces = spaces / 2;
int rspaces = spaces - lspaces;
for(int i = 0; i < lspaces; i++)
System.out.print(" ");
System.out.print(text);
for(int i = 0; i < rspaces; i++)
System.out.print(" ");
}
public static void main(String[] args) {
Node r = new Node(10);
r.left = new Node(5);
r.left.left = new Node(2);
r.left.left.left = new Node(1);
r.left.right = new Node(4);
r.right = new Node(20);
r.right.left = new Node(17);
r.right.right = new Node(22);
r.right.right.left = new Node(21);
r.right.right.right = new Node(25);
printTree(r);
}
#include<iostream>
using namespace std;
template<class T>
class Node {
public :
Node<T>( const T& value, Node<T> * left, Node<T> * right ) :
_value(value),
_left(left),
_right(right),
_padding(0),
_level(0) {
if(_left != NULL) {
_padding = _left->maxPadding() + 1;
_left->updateLevel(1);
}
if(_right != NULL) {
_right->addPadding(_padding + 1);
_right->updateLevel(1);
}
}
void addPadding(int p) {
_padding += p;
if(_left != NULL) _left->addPadding(p);
if(_right != NULL) _right->addPadding(p);
}
void updateLevel(int l) {
_level += l;
if(_left != NULL) _left->updateLevel(l);
if(_right != NULL) _right->updateLevel(l);
}
int maxPadding() {
if(_right == NULL) return _padding;
else return _right->maxPadding();
}
T getValue() { return _value; }
int getPadding() { return _padding; }
int getLevel() { return _level; }
Node<T> * getLeft() { return _left; }
Node<T> * getRight() { return _right; }
private :
T _value;
Node<T> * _left;
Node<T> * _right;
int _padding;
int _level;
};
typedef Node<int> * NP;
queue<NP> q;
void print(NP node) {
int currLevel = node->getLevel();
int currPadding = 0;
q.push(node);
while(!q.empty()) {
NP n = q.front();
q.pop();
if(n->getLevel() == (currLevel + 1) ) {
cout<<endl;
cout<<endl;
currLevel = n->getLevel();
currPadding = 0;
}
for(int i = currPadding; i <= n->getPadding(); i++)
cout<<"\t";
cout<<(n->getValue() * 100);
currPadding = n->getPadding() + 1;
if(n->getLeft() != NULL)
q.push(n->getLeft());
if(n->getRight() != NULL)
q.push(n->getRight());
}
return;
}
int main() {
NP leaf1 = new Node<int>(4, NULL, NULL);
NP leaf2 = new Node<int>(5, NULL, NULL);
NP node1 = new Node<int>(2, leaf1, leaf2);
NP leaf3 = new Node<int>(6, NULL, NULL);
NP leaf4 = new Node<int>(7, NULL, NULL);
NP node2 = new Node<int>(3, leaf3, leaf4);
NP tree = new Node<int>(1, node1, node2);
print(tree);
return 0;
}
typedef struct __TreeNode
{
unsigned int val;
__TreeNode *left;
__TreeNode *right;
__TreeNode (unsigned int val) : val(val), left(NULL), right(NULL) {}
}TreeNode;
int getDigitCount(unsigned int n) {
if(n == 0) return 1;
int d = 0;
while(n) {
++d;
n /= 10;
}
return d;
}
void getMinMaxVerticalLevel(TreeNode *root, int curL, int &minL, int &maxL, int &maxDigits) {
if(root == NULL)
return;
if(curL < minL) minL = curL;
if(curL > maxL) maxL = curL;
int digitCount = getDigitCount(root->val);
if(digitCount > maxDigits)
maxDigits = digitCount;
getMinMaxVerticalLevel(root->left, curL - 1, minL, maxL, maxDigits);
getMinMaxVerticalLevel(root->right, curL + 1, minL, maxL, maxDigits);
}
void itoa(char *str, unsigned int n) {
if(n == 0) {
*str = '0';
return;
}
char *orgStr = str; unsigned int r = 0;
while(n) {
r = n % 10;
n /= 10;
*(str++) = '0' + r;
}
--str;
while(orgStr < str)
swap(*(orgStr++), *(str--));
}
void PrintTree(TreeNode *root) {
if(root == NULL) return;
int minL = INT_MAX, maxL = INT_MIN, maxDigits = 0;
getMinMaxVerticalLevel(root, 0, minL, maxL, maxDigits);
int totalL = maxL - minL + 1;
string lineStr;
queue<TreeNode*> nodeQ; queue<int> levelQ;
nodeQ.push(NULL); levelQ.push(0);
nodeQ.push(root); levelQ.push(0);
int curL = 0, curD = 0;
bool lineFilled = false;
while(!nodeQ.empty()) {
root = nodeQ.front(); nodeQ.pop();
curL = levelQ.front(); levelQ.pop();
if(root == NULL) {
if(lineFilled) cout << lineStr.c_str() << endl;
while(!nodeQ.empty() && nodeQ.front() == NULL) {
nodeQ.pop(); levelQ.pop();
}
if(nodeQ.empty()) break;
lineStr = string(totalL * maxDigits, ' ');
lineFilled = false;
nodeQ.push(NULL); levelQ.push(0);
}
else {
if(root->left) {
nodeQ.push(root->left); levelQ.push(curL - 1);
}
if(root->right) {
nodeQ.push(root->right); levelQ.push(curL + 1);
}
curD = getDigitCount(root->val);
itoa(&lineStr[maxDigits * (curL - minL) + ((maxDigits - curD) >> 1)], root->val);
lineFilled = true;
}
}
}
int main() {
TreeNode node10(10), node5(5), node15(15), node2(2), node8(8), node18(18), node7(7);
node10.left = &node5; node10.right = &node15;
node15.right = &node18; node5.left = &node2; node5.right = &node8; node8.left = &node7;
PrintTree(&node10);
return 0;
}
public static class Node {
public Node leftChild;
public Node rightChild;
public int value;
public Node(Node leftChild, Node rightChild, int value) {
super();
this.leftChild = leftChild;
this.rightChild = rightChild;
this.value = value;
}
}
public static void printTreeBfsReadOrder(Node root) {
if (root == null)
return;
Queue<Node> nodeQ = new LinkedList<Node>();
Map<Integer, String> depthQ = new HashMap<Integer, String>();
nodeQ.add(root);
getChildMaxIndex(depthQ, 1, 0, root);
for (Iterator iterator = depthQ.values().iterator(); iterator.hasNext();) {
String node = (String) iterator.next();
System.out.println(node);
}
}
private static int getChildMaxIndex(Map<Integer, String> depthQ, int depth,
int parentIndex, Node root) {
if (root == null)
return 0;
int leftIndex = 0;
if (root.leftChild != null) {
leftIndex = getChildMaxIndex(depthQ, depth + 1, parentIndex,
root.leftChild);
}
int rightIndex = 0;
if (root.rightChild != null) {
rightIndex = getChildMaxIndex(depthQ, depth + 1, leftIndex
+ parentIndex + 1, root.rightChild);
}
if (!depthQ.containsKey(depth))
depthQ.put(depth, "");
String str = depthQ.get(depth);
for (int i = str.length(); i < leftIndex + parentIndex; i++) {
str += " ";
}
str += root.value;
for (int i = str.length(); i < rightIndex; i++) {
str += " ";
}
depthQ.put(depth, str);
return leftIndex + rightIndex + 1;
}
guys will this work
public class Solution {
LinkedList<TreeNode> queue = null;
LinkedList<Integer> list = null;
int maxDepth = 0;
void levelOrder(TreeNode root) {
queue.add(root);
list.add(root.val);
int depth = 0;
while (!queue.isEmpty()) {
for (int i = 0; i < Math.pow(2, depth); i++) {
TreeNode p = queue.removeFirst();
if (p == null) {
queue.add(null);
list.add(0);
queue.add(null);
list.add(0);
}
else {
queue.add(p.left);
if (p.left == null) {
list.add(0);
}
else {
list.add(p.left.val);
}
queue.add(p.right);
if (p.right == null) {
list.add(0);
}
else {
list.add(p.right.val);
}
}
}
depth++;
if (depth == maxDepth) {
break;
}
}
}
void drawBT(TreeNode root) {
queue = new LinkedList<TreeNode>();
list = new LinkedList<Integer>();
getDepth();
levelOrder(root);
for (int i = 0; i < maxDepth + 1; i++) {
int dis = (int)Math.pow(2, maxDepth - i);
StringBuilder sdis = new StringBuilder();
for (int k = 0; k < dis; k++) {
sdis.append(" ");
}
for (int j = 0; j < Math.pow(2, i); j++) {
if (j == 0) {
System.out.print(sdis.toString());
}
else {
System.out.print(sdis.toString());
System.out.print(sdis.toString());
}
System.out.print(list.removeFirst());
}
System.out.println("");
}
}
}
Here is the C++ version of solution using in-order search and BFS.
Running time is O(N).
Printing the indentation was little tricky.
#include<list>
#include<iostream>
using namespace std;
struct node {
int value;
int offset;
node * left;
node* right;
node(int v):value(v), left(0), right(0), offset(-1){}
};
int offset = 0;
void inorder(node *t)
{
if (!t)
return;
inorder(t->left);
t->offset = offset++;
inorder(t->right);
}
void printTree(node *t)
{
int cur_children = 0;
int next_children = 0;
int last_off = INT_MIN;
inorder(t);
list<node *> queue;
queue.push_back(t);
cur_children++;
while(queue.size())
{
node * cur = queue.front();
queue.pop_front();
if (cur->left)
{
queue.push_back(cur->left);
next_children++;
}
if (cur->right)
{
queue.push_back(cur->right);
next_children++;
}
int gap = (last_off == INT_MIN)? (cur->offset) : (cur->offset - last_off -1);
for(int i = 0; i < gap; i++)
cout<<" ";
cout<< cur->value;
last_off = cur->offset;
cur_children--;
if (cur_children == 0)
{
last_off = INT_MIN;
cout<<endl;
cur_children = next_children;
next_children = 0;
}
}
}
- SK December 31, 2014courtesy : http : // stackoverflow . com/a/4973083/3010355 Just replaced TreeNode structure static class TreeNode { public TreeNode left; public int key; public TreeNode right; public TreeNode (int k) { this.left = null; this.key = k; this.right = null; } } class BTreePrinter { public static void printNode(TreeNode root) { int maxLevel = BTreePrinter.maxLevel(root); printNodeInternal(Collections.singletonList(root), 1, maxLevel); } private static void printNodeInternal(List<TreeNode> nodes, int level, int maxLevel) { if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes)) return; int floor = maxLevel - level; int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0))); int firstSpaces = (int) Math.pow(2, (floor)) - 1; int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1; BTreePrinter.printWhitespaces(firstSpaces); List<TreeNode> newNodes = new ArrayList<TreeNode>(); for (TreeNode node : nodes) { if (node != null) { System.out.print(node.key); newNodes.add(node.left); newNodes.add(node.right); } else { newNodes.add(null); newNodes.add(null); System.out.print(" "); } BTreePrinter.printWhitespaces(betweenSpaces); } System.out.println(""); for (int i = 1; i <= endgeLines; i++) { for (int j = 0; j < nodes.size(); j++) { BTreePrinter.printWhitespaces(firstSpaces - i); if (nodes.get(j) == null) { BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1); continue; } if (nodes.get(j).left != null) { System.out.print("/"); } else BTreePrinter.printWhitespaces(1); BTreePrinter.printWhitespaces(i + i - 1); if (nodes.get(j).right != null) System.out.print("\\"); else BTreePrinter.printWhitespaces(1); BTreePrinter.printWhitespaces(endgeLines + endgeLines - i); } System.out.println(""); } printNodeInternal(newNodes, level + 1, maxLevel); } private static void printWhitespaces(int count) { for (int i = 0; i < count; i++) System.out.print(" "); } private static int maxLevel(TreeNode node) { if (node == null) return 0; return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1; } private static <T> boolean isAllElementsNull(List<T> list) { for (Object object : list) { if (object != null) return false; } return true; }