Google Interview Question SDE-2s
Country: India
Interview Type: In-Person
The question says with proper formatting. So we have to start by finding the order and height of the tree.
If the tree is binary and its height is 4. Then the last level cannot have more than 2^4 nodes. So provide space for those nodes and the space between them depends on level 3 nodes. Space between level 3 in turn depends of level 2 ....Root level.
To draw this tree - The formatting should be done for each and every level - which in turn depends on nodes present in the subsequent levels.
Consider a hashmap with levels as keys and list of nodes as values. Add a string variable "formatTree" to each node. Pass each level (BFS). As you do BFS, update the nodes of previous levels with a "TAB" for every 2 nodes in the current level. (If odd, one tab. Even two tabs). This will align the previous nodes properly.
In the same way, do for the next level. A print function can concatenate and print the tree.
/**
6
/ | \
2 10 7
/ \ \
1 4 9
/ \ / / | \
3 5 8 12 13 14
*/
public class PrintTreeInLevelWiseFormat {
static class Node {
int value;
Node children[];
public Node(int value, Node[] children) {
super();
this.value = value;
this.children = children;
}
}
public static void printLevelWiseTree(List<Node> nodes) {
if(nodes == null || nodes.isEmpty()){
return;
}
else{
List<Node> next = new ArrayList<Node>();
for(Node node : nodes) {
System.out.print(node.value+" ");
if(node.children != null){
for(Node child : node.children){
next.add(child);
}
}
}
System.out.println();
printLevelWiseTree(next);
}
}
public static void main(String[] args) {
Node node14 = new Node(14, null);
Node node13 = new Node(13, null);
Node node12 = new Node(12, null);
Node children9[] = {node12, node13, node14};
Node node9 = new Node(9, children9);
Node node8 = new Node(8, null);
Node children4[] = {node8};
Node node4 = new Node(4, children4);
Node node5 = new Node(5, null);
Node node3 = new Node(3, null);
Node children1[] = {node3, node5};
Node node1 = new Node(1, children1);
Node children7[] = {node9};
Node node7 = new Node(7, children7);
Node children2[] = {node1, node4};
Node node2 = new Node(2, children2);
Node node10 = new Node(10, null);
Node children6[] = {node2, node10, node7};
Node root1 = new Node(6, children6);
List<Node> rootList = new ArrayList<Node>();
rootList.add(root1);
printLevelWiseTree(rootList);
}
}
/* This can be done as a DFS problem...the recursive solution should be straightforward.
* This is an iterative solution using stacks (for the lolz) */
public class
DrawTree
{
public static class
Node
{
Node[] ns;
public Node (Node... ns) { this.ns = ns; }
Node[] GetChildren() { return this.ns; }
}
/* I will try an iterative solution, since I don't do those very often */
/* Note: The iterative solution was harder than expected: it takes a little more effort to
* visualize. I ended up using multiple stacks, to track the state at each tree level */
public static String
DT
(Node root)
{
List<StringBuilder> sbs = new ArrayList<StringBuilder>();
int offset = 0;
Stack<Node> s = new Stack<>();
Stack<Integer> is = new Stack<>();
s.push(root);
is.push(s.size());
while (s.size() > 0) {
Node n = s.pop();
while (is.peek() == 0) is.pop();
Integer siblings_remaining = is.pop() - 1;
if (sbs.size() <= is.size()) sbs.add(is.size(), new StringBuilder());
sbs.get(is.size()).setLength(offset + 1);
sbs.get(is.size()).setCharAt(offset, 'N');
is.push(siblings_remaining);
if (n.GetChildren().length > 0) {
for (int i = n.GetChildren().length - 1; i >= 0; --i)
s.push(n.GetChildren()[i]);
is.push(n.GetChildren().length);
} else offset++;
}
StringBuffer ret = new StringBuffer();
for (StringBuilder sb : sbs)
ret.append(sb).append("\n");
return ret.toString();
}
The tree will end up looking like this:
1
2----5---------10
3-4-6-7-8-9-11
where it is clear who is the parent and who is the child. The algorithm works by incrementing an offset from the start of the line when children are being output, and
when backtracking, but not when following a child pointer.
width(Node) = sum( width(ChildNodes)) caqlculate recursively , and save it in a hashMap widthArr[node]
Using this you can calculates the coordinates of each node in a 2D space.
Position[Node].x=position[firstNode].x + sum(width[ChildNodesBeforeNode ])+width[Node]/2
//position[firstNode].x =position[ParentNode].x-width[parentNode]/2+width[firstNode]/2
position[Node].y=position[parentNode].y+1
Here's the code for pretty printing a binary tree in Python:
import StringIO
class Queue(object):
def __init__(self):
self.a = []
def enqueue(self, b):
self.a.insert(0, b)
def dequeue(self):
return self.a.pop()
def isEmpty(self):
return self.a == []
def size(self):
return len(self.a)
def getheight(node):
if not node:
return 0
else:
return max(getheight(node.left), getheight(node.right)) + 1
def add_padding(ipstr, pad_length):
ipstr = ipstr.strip()
padding = ' ' * (pad_length - len(ipstr))
return ''.join([padding, ipstr])
def show(root):
max_pretty_print_height = 7
output = StringIO.StringIO()
keys = []
if root:
current_level = Queue()
next_level = Queue()
current_level.enqueue(self.root)
depth = 0
while not current_level.isEmpty():
current_node = current_level.dequeue()
output.write('%s ' % current_node.key if current_node else 'NUL ')
next_level.enqueue(current_node.left if current_node else current_node)
next_level.enqueue(current_node.right if current_node else current_node)
if current_level.isEmpty():
if sum([i is not None for i in next_level.a]):
current_level, next_level = next_level, current_level
depth = depth + 1
output.write('\n')
if getheight(root) < max_pretty_print_height:
pretty_output = pretty_print(output, depth)
output.close()
print pretty_output.getvalue()
pretty_output.close()
else:
print output.getvalue()
output.close()
def pretty_print(output, depth):
pad_length = 3
pretty_output = StringIO.StringIO()
spaces = int(math.pow(2, depth))
output.seek(0)
while spaces > 0:
skip_start = spaces * pad_length
skip_mid = (2 * spaces - 1) * pad_length
key_start_spacing = ' ' * skip_start
key_mid_spacing = ' ' * skip_mid
keys = output.readline().split(' ')
padded_keys = (self.add_padding(key, pad_length) for key in keys)
padded_str = key_mid_spacing.join(padded_keys)
complete_str = ''.join([key_start_spacing, padded_str])
pretty_output.write(complete_str)
current_depth = spaces
spaces = spaces // 2
if spaces > 0:
pretty_output.write('\n')
cnt = 0
while cnt < current_depth:
inter_symbol_spacing = ' ' * (pad_length + 2 * cnt)
symbol = ''.join(['/', inter_symbol_spacing, '\\'])
symbol_start_spacing = ' ' * (skip_start-cnt-1)
symbol_mid_spacing = ' ' * (skip_mid-2*(cnt+1))
pretty_output.write(''.join([symbol_start_spacing, symbol]))
for i in keys[1:-1]:
pretty_output.write(''.join([symbol_mid_spacing, symbol]))
pretty_output.write('\n')
cnt = cnt + 1
return pretty_output
For example:
>>> t = Tree()
>>> show(t.root)
Will print something like this
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1 7
/ \ / \
/ \ / \
/ \ / \
/ \ / \
0 2 5 8
Sorry, the career cup formatting is not the most optimal. The real output looks much better.
This is a Breadth First Search(BFS) problem where you start from the Root node and print it. Then examine its children. Assuming they exist, print them on the same line and move on to examine children of both the children of the Root node.
- DrFrag September 20, 2013Although BFS can be easily implemented by using a Queue to maintain a list of nodes in the order in which we reach them, the challenge lies in trying to print each node on a line on the Console that represents its level in the Binary Tree.
eg:
Input is a Binary tree
Root -> 1
/ \
2 3
/ \ / \
4 5 6 7
Output on the console is
1
23
4567
Hope this clarifies the question.