Linkedin Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
/*
Here is my take with C program.
1
/\
35
/\\
2 47
/\\
9 68
===========
Expected Output:
1
35
247
968
*/
#include <stdio.h>
#include <stdlib.h>
#define LCHILD 1
#define RCHILD 0
typedef struct Tree {
int item;
struct Tree *lchild;
struct Tree *rchild;
} node;
node * createNode(int item) {
node * newnode = (node *) malloc(sizeof(node));
newnode->lchild = NULL;
newnode->rchild = NULL;
newnode->item = item;
return newnode;
}
typedef struct Treenodelist {
node * current;
struct Treenodelist * next;
} nodelist;
static nodelist *head, *tail;
nodelist * enqueue(node *n) {
nodelist *temp = (nodelist *) malloc(sizeof(nodelist));
temp->current = n;
temp->next = NULL;
if (tail == NULL) {
tail = temp;
return tail;
}
while (tail->next != NULL) {
tail->next = tail;
}
tail->next = temp;
return tail->next;
}
node* dequeue() {
if (head == NULL) {
return NULL;
}
nodelist * temp=head;
head=head->next;
return temp->current;
}
void printTree(node *n) {
if (n == NULL) {
return;
}
tail = NULL;
tail = enqueue(n);
head = tail;
node * m1 = createNode(-1);
tail = enqueue(m1);
while (head != NULL) {
node *temp;
temp = dequeue();
if (temp->item == -1) {
printf("\n");
if (head != NULL) {
tail = enqueue(m1);
}
}
else {
printf("%d", temp->item);
if (temp->lchild != NULL) {
tail = enqueue(temp->lchild);
if (head == NULL) head = tail;
}
if (temp->rchild != NULL) {
tail = enqueue(temp->rchild);
if (head == NULL) head = tail;
}
}
}
}
int main() {
node * n1 = createNode(1);
node * n2 = n1->lchild = createNode(3);
node * n3 = n1->rchild = createNode(5);
node * n4 = n2->lchild = createNode(2);
node * n5 = n2->rchild = createNode(4);
node * n6 = n3->rchild = createNode(7);
node * n7 = n4->lchild = createNode(9);
node * n8 = n4->rchild = createNode(6);
node * n9 = n5->rchild = createNode(8);
printTree(n1);
return 0;
}
Simple O(n) complexity, O(n) non-recursive BFS traversal:
public void printTree(Node root){
if(root == null){
return;
}
LinkedList<Node> list = new LinkedList<Node>();
LinkedList<Node> children = new LinkedList<Node>();
LinkedList<Node> temp;
StringBuilder line = new StringBuilder();
Node node, child;
list.add(root);
while(!list.isEmpty()){
while(!list.isEmpty()){
node = list.removeFirst();
line.append(node.value);
child = node.left;
if(child != null){
children.add(child);
}
child = node.right;
if(child != null){
children.add(child);
}
}
java.lang.System.out.println(line.toString());
line.setLength(0);
temp = children;
children = list;
list = temp;
}
}
public void print() {
if (rootNode == null) {
System.out.println("Tree is empty");
return;
}
ArrayDeque<Node> parentQueue = new ArrayDeque<Node>();
ArrayDeque<Node> childQueue = new ArrayDeque<Node>();
ArrayDeque<Node> temp;
parentQueue.add(rootNode);
StringBuilder sb = new StringBuilder();
while (!parentQueue.isEmpty()) {
Node node = parentQueue.pop();
sb.append(node.value);
if (node.left != null) {
childQueue.add(node.left);
}
if (node.right != null) {
childQueue.add(node.right);
}
if (parentQueue.isEmpty()) {
System.out.println(sb);
sb.setLength(0);
if (!childQueue.isEmpty()) {
temp = childQueue;
childQueue = parentQueue;
parentQueue = temp;
}
}
}
}
This is the C++ version of solution using BFS.
#include<list>
#include<iostream>
using namespace std;
struct Node {
int value;
Node * left;
Node * right;
Node(int v):value(v),left(0), right(0){}
};
void printTree(Node * root)
{
list<Node *> queue;
int cur_children = 1;
int next_children = 0;
queue.push_back(root);
while (queue.size())
{
Node* cur = queue.front();
queue.pop_front();
if (cur->left)
{
next_children++;
queue.push_back(cur->left);
}
if ( cur->right)
{
next_children++;
queue.push_back(cur->right);
}
cout<<cur->value<<" ";
cur_children--;
if (cur_children==0)
{
cout<<endl;
cur_children = next_children;
next_children = 0;
}
}
}
int main()
{
Node * root = new Node(1);
Node * n3 = new Node(3);
Node * n5 = new Node(5);
Node * n2 = new Node(2);
Node * n4 = new Node(4);
Node * n7 = new Node(7);
Node * n9 = new Node(9);
Node * n6 = new Node(6);
Node * n8 = new Node(8);
root->left = n3;
root->right = n5;
n3->left = n2;
n3->right = n4;
n5->left = n7;
n2->left = n9;
n2->right = n6;
n4->left = n8;
printTree(root);
return 1;
}
// C++ Print levels
// Variable count tracks the number of nodes at a specific level.
// We know that first level has count '1'
// We first process nodes at the level, and enqueue its children in the queue.
// Once we have processed all nodes at a specific level (as indicated by count == 0),
// the queue then has nodes that belong to the next level
void levels(node * n) {
queue<node *> q;
q.enqueue(n);
int count = 1; // Queue has one node at this level
while(!q.empty()) {
node * n1 = q.top();
if (n1->l) {
q.enqueue(n1->l);
}
if (n1->r) {
q.enqueue(n1->r);
}
q.dequeue();
count--; // We processed a node, decrement count
if (count == 0) { // count will be zero when a level is completely processed
count = q.size(); // Get the count of node at next level
}
}
}
// C++ Print levels
// Variable count tracks the number of nodes at a specific level.
// We know that first level has count '1'
// We first process nodes at the level, and enqueue its children in
// the queue.
// Once we have processed all nodes at a specific level
// (as indicated by count == 0),
// the queue then has nodes that belong to the next level
class node {
public:
node *l, *r;
int v;
};
void levels(node * n) {
queue<node *> q;
q.enqueue(n);
int count = 1; // Queue has one node at this level
while(!q.empty()) {
node * n1 = q.top();
cout << n1->v << " ";
if (n1->l) {
q.enqueue(n1->l);
}
if (n1->r) {
q.enqueue(n1->r);
}
q.dequeue();
count--; // We processed a node, decrement count
if (count == 0) { // count will be zero when a level is completely processed
cout << endl;
count = q.size(); // Get the count of nodes at next level
}
}
}
Looks like I have found a way to solve the problem using O(n). "Index" indicates the current node which I visit. NextIndex tells me at which "index" should I add the '\n'. Once I add it, I just sum the number of nodes of the current queue (because it tels me how many children are in the next level).
public static void printTree(Node root)
{
if(root==null) System.out.println("");
else{
StringBuilder builder = new StringBuilder();
LinkedBlockingQueue<Node> queue = new LinkedBlockingQueue<Node>();
queue.add(root);
int index=0,nextIndex=1;
while(!queue.isEmpty())
{
index++;
Node current=queue.poll();
if(current!=null)
{
builder.append(current.value);
if(current.left!=null)
{
queue.add(current.left);
}
if(current.right!=null)
{
queue.add(current.right);
}
}
if(index==nextIndex)
{
nextIndex+=queue.size();
builder.append("\n");
}
}
System.out.println(builder.toString());
}
}
public void printTree(Node root) {
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
int numNodesAtlevel = q.size();
while (numNodesAtlevel > 0){
Node a= q.poll();
System.out.print(a.value +" ");
if(a.left != null)
q.add(a.left);
if(a.right != null)
q.add(a.right);
numNodesAtlevel --;
}
System.out.println();
}
}
- Vir Pratap Uttam June 03, 2015