Groupon Interview Question
Software EngineersCountry: United States
And What do you mean that tree can have any number of nodes? can't we do a simple BFS and print the nodes?
What about the number of nodes in each level, is there any restriction for that?
private static void levelOrderTraversal(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
q.add(root);
q.add(new BinaryTreeNode(-1));
while (!q.isEmpty()) {
temp = q.poll();
if (temp.getData() == -1) {
System.out.println();
if (!q.isEmpty())
q.add(new BinaryTreeNode(-1));
} else {
System.out.print(" "+temp.getData());
if (temp.getLeft() != null)
q.add(temp.getLeft());
if (temp.getRight() != null)
q.add(temp.getRight());
}
}
}
/**
* Write a function to print a tree, which can have any number of nodes,
* in level order, each level on a new line. E.g.,
* If the tree is :
* 1
* 2 3
* 4 5 6
* then the answer should be:
* 1\n
* 2,3\n
* 4,5,6\n
*/
exports.Node = function (value, children) {
this.value = value;
this.child = [];
for (var i = 0; i < children.length; i++) {
this.child.push(children[i]);
}
};
exports.printTree = function (rootNode) {
var Q = [];
Q.enqueue = Q.unshift;
Q.dequeue = Q.pop;
rootNode.visited = true;
rootNode.level = 0;
Q.enqueue(rootNode);
var currLevel = 0;
var s = "";
while (Q.length) {
var p = Q.dequeue();
if (p.level === currLevel) {
s += p.value;
}
if (p.level === currLevel + 1) {
s += '\n';
s += p.value;
currLevel++;
}
if (Q.length && Q[Q.length - 1].level === p.level) {
s += ',';
}
for (var i = 0; i < p.child.length; ++i) {
if (!p.child[i].visited) {
p.child[i].visited = true;
p.child[i].level = p.level + 1;
Q.enqueue(p.child[i]);
}
}
}
return s;
};
jest.dontMock('../2015-06-25');
describe('A function to print a tree in level order, ' +
'each level on a new line.', function () {
it('prints each level on its own line', function () {
var printTree = require('../2015-06-25').printTree
, Node = require('../2015-06-25').Node
rootNode = new Node(1, [
new Node(2, [
new Node (4, [])
]),
new Node(3, [
new Node(5, []),
new Node(6, [])
])
]);
expect(printTree(rootNode)).toBe([
"1",
"2,3",
"4,5,6"
].join("\n"));
});
});
/**
* Write a function to print a tree, which can have any number of nodes,
* in level order, each level on a new line. E.g.,
* If the tree is :
* 1
* 2 3
* 4 5 6
* then the answer should be:
* 1\n
* 2,3\n
* 4,5,6\n
*/
exports.Node = function (value, children) {
this.value = value;
this.child = [];
for (var i = 0; i < children.length; i++) {
this.child.push(children[i]);
}
};
exports.printTree = function (rootNode) {
var Q = [];
Q.enqueue = Q.unshift;
Q.dequeue = Q.pop;
rootNode.visited = true;
rootNode.level = 0;
Q.enqueue(rootNode);
var currLevel = 0;
var s = "";
while (Q.length) {
var p = Q.dequeue();
if (p.level === currLevel) {
s += p.value;
}
if (p.level === currLevel + 1) {
s += '\n';
s += p.value;
currLevel++;
}
if (Q.length && Q[Q.length - 1].level === p.level) {
s += ',';
}
for (var i = 0; i < p.child.length; ++i) {
if (!p.child[i].visited) {
p.child[i].visited = true;
p.child[i].level = p.level + 1;
Q.enqueue(p.child[i]);
}
}
}
return s;
};
In Go :
type TNode struct {
Value int
Left *TNode
Right *TNode
Level int
}
func DisplayBFS(root *TNode) {
if root == nil {
return
}
queue := NewQueue()
currentLevel := 0
nbItemByLevel := 0
queue.Enqueue(root)
for {
if queue.IsEmpty() {
return
}
current := queue.Dequeue().(*TNode)
if currentLevel != current.Level {
fmt.Println("")
currentLevel++
nbItemByLevel = 0
}
if nbItemByLevel > 0 {
fmt.Print(",")
}
fmt.Print(current.Value)
nbItemByLevel++
if current.Left != nil {
current.Left.Level = current.Level + 1
queue.Enqueue(current.Left)
}
if current.Right != nil {
current.Right.Level = current.Level + 1
queue.Enqueue(current.Right)
}
}
}
import java.util.LinkedList;
/**
* Created by Ryan on 12/8/2015.
*/
public class Test
{
public static class Node
{
int data;
Node[] children;
public Node( int data, Node[] children )
{
this.data = data;
this.children = children;
}
}
public static void main(String args[])
{
//Testy test
/*
0
/|\
1 2 3
/ /\
4 5 6
/ /|\
7 8 9 10
*/
Node leaf1 = new Node(4, null);
Node leaf2 = new Node(7, null);
Node leaf3 = new Node(8, null);
Node leaf4 = new Node(9, null);
Node leaf5 = new Node(10, null);
Node inner5 = new Node(6, new Node[]{leaf3, leaf4, leaf5});
Node inner4 = new Node(5, new Node[]{leaf2});
Node inner3 = new Node(3, null);
Node inner2 = new Node(2, new Node[]{inner4, inner5});
Node inner1 = new Node(1, new Node[]{leaf1});
Node root = new Node(0, new Node[]{inner1, inner2, inner3});
printTree(root);
}
public static void printTree(Node root)
{
LinkedList<Node> current = new LinkedList<>();
if(root == null)
return;
current.add(root);
while(current.size() > 0)
{
printLevel(current);
LinkedList<Node> parents = current;
current = new LinkedList<>();
for(Node parent : parents)
{
if( parent.children != null)
{
for (Node c : parent.children)
{
current.add(c);
}
}
}
}
}
public static void printLevel( LinkedList<Node> level)
{
if(level.size() <= 0)
{
return;
}
StringBuilder str = new StringBuilder();
for(Node c : level)
{
if (str.length() > 0)
{
str.append(", ");
}
str.append(c.data);
}
System.out.println(str);
}
}
void printTreeWithDepth( Tree root){
List<Tree> treeList = new ArrayList<Tree>();
Queue<Tree> queue = new LinkedList<Tree>();
queue.add(root);
System.out.print(root.value);
while(!queue.isEmpty()){
Tree tempNode= queue.poll();
Tree unprintedNode = null;
while((unprintedNode =getUnPrintedTreeNode(tempNode, treeList))!= null){
System.out.print(unprintedNode.value+" ");
treeList.add(unprintedNode);
queue.add(unprintedNode);
}
}
}
Tree getUnPrintedTreeNode(Tree node, List<Tree> treeList){
for(Tree n :node.nodes)
if(!treeList.contains(n)){
return n;
}
return null;
}
void printTreeWithDepth( Tree root){
List<Tree> treeList = new ArrayList<Tree>();
Queue<Tree> queue = new LinkedList<Tree>();
queue.add(root);
System.out.print(root.value);
while(!queue.isEmpty()){
Tree tempNode= queue.poll();
Tree unprintedNode = null;
while((unprintedNode =getUnPrintedTreeNode(tempNode, treeList))!= null){
System.out.print(unprintedNode.value+" ");
treeList.add(unprintedNode);
queue.add(unprintedNode);
}
}
}
Tree getUnPrintedTreeNode(Tree node, List<Tree> treeList){
for(Tree n :node.nodes)
if(!treeList.contains(n)){
return n;
}
return null;
}
void printTreeWithDepth( Tree root){
List<Tree> treeList = new ArrayList<Tree>();
Queue<Tree> queue = new LinkedList<Tree>();
queue.add(root);
System.out.print(root.value);
while(!queue.isEmpty()){
Tree tempNode= queue.poll();
Tree unprintedNode = null;
while((unprintedNode =getUnPrintedTreeNode(tempNode, treeList))!= null){
System.out.print(unprintedNode.value+" ");
treeList.add(unprintedNode);
queue.add(unprintedNode);
}
}
}
Tree getUnPrintedTreeNode(Tree node, List<Tree> treeList){
for(Tree n :node.nodes)
if(!treeList.contains(n)){
return n;
}
return null;
}
In it a binary tree? if not, how are the children stored in the tree?
- MehrdadAP June 25, 2015