Linkedin Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

My answer

class TreePrinter {
 
  static class Node {
    int value;
    Node left;
    Node right;
  }
 
  public void printTree(Node root) {
    
    Queue<Node> queue = new Queue<Node>();
    
    if(root == NULL)
        return;
    
    queue.enqueue(root);
    
    List<Node> list;
    
    while(!queue.IsEmpty())
    {
        list = new List<node>();  // Initialize a new list
        
        while(!.queue.IsEmpty())
        {
            Node u = queue.dequeue(); //Remove the first element in the queue
        
            if(u.Left != NULL) { list.add(u.Left); }
            if(u.Right != NULL) { list.add(u.Right); }
            
            Console.Print(u.data + " ");
        }
        
        Console.PrintLine();
        
        // Add the enxt level to the queue
        foreach(Node n in list)
        {
            queue.enqueue(n);
        }
    }        
  }
}

- PrateekS. July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, I think in the code ,there are two queues.The first queue add all of the root nodes, the seconde queues add all of the children of the first queue. Take turns to save the nodes.

- fenghanlu November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

function Node(data) {
    this.data = data;
    this.left = null;
    this.right = null;
}

function LevelItem(level, node) {
    this.level = level;
    this.node = node;
}

var head = new Node(1);
head.left = new Node(3);
head.right = new Node(5);
head.right.right = new Node(7);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(9);
head.left.right.right = new Node(8);

function printByLevel() {
    var item, levels = {}, stack = [new LevelItem(0, head)];
    
    while (stack.length > 0) {
        item = stack.pop();
        
        if (item.node.right) {
            stack.push(new LevelItem(item.level + 1, item.node.right));
        }
        
        if (item.node.left) {
            stack.push(new LevelItem(item.level + 1, item.node.left));
        }
        
        if (levels[item.level]) {
          levels[item.level].push(item);
        } else {
          levels[item.level] = [item];
        }
    }
    
    Object.keys(levels).forEach(function (level) {
      var itemsToBePrinted = [];
        
      levels[level].forEach(function (item) {
         itemsToBePrinted.push(item.node.data);
      });
      
      console.log.apply(console, itemsToBePrinted);
    });
}

printByLevel();

- qwerty August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thank you for the contribution, Prateek.

I am not quite sure what you are doing with the extra list there, since you already appear to have a queue that may be able to handle all that you need from it. Have you considered reducing it to the following?

Queue<Node> q = new Queue<Node>(new[] { tree });
while (q.Count > 0)
{
    Node n = q.Dequeue();                
    if (n == null) continue;
    Console.WriteLine(n.Value);
    q.Enqueue(n.Left);
    q.Enqueue(n.Right);
}

- Someone August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh! I see it now! I should not have posted so soon. You do not simply want a level traversal, you also want elements on the same level on the same line.

- Someone August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In that case, I guess we could insert markers into the queue to signify that we have started a new level. I have tested the following with a simple tree.

Queue<Node> q = new Queue<Node>(new[] { tree, new Node() });
while (q.Count > 0)
{
    Node n = q.Dequeue();                
    if (n == null) continue;
    if (n.Value == -1)
    {
        Console.WriteLine();
        if (q.Count == 0) { break; }
        q.Enqueue(new Node());
        continue;
    }

    Console.Write(n.Value + " ");
    q.Enqueue(n.Left);
    q.Enqueue(n.Right);
}

A node with a value of -1 is a marker. It is the default value of a node, so I add one after the root of the queue initialization. Whenever a marker node is encountered, I know the level is used up. When a level is used up, I also know that the nodes of the next level are already sitting in the queue waiting, so I insert a new marker to the end of the queue at the same time. This should work, regardless of how many nodes there are on any level, because all children are added to the queue before the next marker is encountered, no matter how large the n of an n-ary tree.

The loop needs to be broken if the last element in the queue was a marker.

- Someone Again August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printByLevel(TreeNode root){
ArrayList<TreeNode> nodes = new ArrayList<TreeNode>( );
TreeNode temp = root;
nodes.add(temp);
int step = 0;
while(nodes.size() > 0){
int size = nodes.size();
for(int i=step ; i<size ; i++){
TreeNode node = nodes.get(i);
System.out.print(node.val);
if(node.left != null){
nodes.add(node.left);
}
if(node.right != null){
nodes.add(node.right);
}
step++;
}
System.out.println();
if(step == nodes.size()){
break;
}
}
}

- Anonymous August 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PrintTreeByLevel {

	public static void printTreeByLevel(TreeNode root) {
		if (root == null)
			return;
		List<TreeNode> currentLevel = new List<TreeNode>();
		currentLevel.add(root);
		while(currentLevel.size>0){
			List<TreeNode> parents= currentLevel;
			currentLevel = new List<TreeNode>();
			for (TreeNode node: parents){
 				System.out.print(node.value+" ");
				if(node.left != null){
					currentLevel .add(node.left);
				}
				if(node.right!= null){
					currentLevel .add(node.right);
				}
			}
			System.out.println();
		}
	}

}

- sLion August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void print(Node node) {
        Queue<Node> nodeArrayDeque = new LinkedList<Node>();

        if (node == null) {
            return;
        }

        List<Node> sameLevelNodes = new ArrayList<Node>();
        sameLevelNodes.add(node);
        while (!sameLevelNodes.isEmpty()) {
            for (Node s : sameLevelNodes) {
                nodeArrayDeque.add(s);
            }

            while (!nodeArrayDeque.isEmpty()) {
                Node u = nodeArrayDeque.remove();
                System.out.println(u.value);
                if (u.left != null) {
                    sameLevelNodes.add(u.left);
                }
                if (u.right != null) {
                    sameLevelNodes.add(u.right);
                }
            }

            System.out.println("");
        }
    }

- Anonymous August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

there should be a list clear after this below code

for (Node s : sameLevelNodes) {
                nodeArrayDeque.add(s);
            }

sameLevelNodes.clear();
.
.
.

- krishna September 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following solution is without Queue or any intermediate data strucutre.

public  Node reverse(Node root)
    {
        Node currentNode = root;
        Node resultNode = null;
        //start with root node that will eventually become the leaf node in the resultNode
        while(currentNode.left() != null)
        {
          //create resultNode from the currentNode
           Node rightNode = new Node(currentNode.right().key(), null, null);
           if(resultNode == null)
           {
               Node leftNode = new Node(currentNode.key(), null, null, false);
               resultNode = new Node(currentNode.left().key(), leftNode, rightNode, false); 
           }
            else    // previous result Node will become left key
           {
              resultNode = new Node(currentNode.left().key(), resultNode, rightNode, false);
           }
           currentNode = currentNode.left();
        }
        return resultNode;
    }

- Andy S September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

remove last param 'false' in this line of the code above

Node leftNode = new Node(currentNode.key(), null, null, false);

- Andy S September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printSameLevel(TreeNode root){
	//Create empty queue
	Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
	
	TreeNode marker = new TreeNode("-1");
	queue.add(root);
	//Add marker for level
	queue.add(marker);
	
	while(!queue.isEmpty()) {
		
			//loop till reach at marker
			while(!queue.peek().data.equalsIgnoreCase("-1")) {
				TreeNode node = queue.poll();
				System.out.print(node + " ");
				if(node.left != null ) queue.add(node.left);
				if(node.right != null ) queue.add(node.right);	
			}
			
			queue.poll();
			
			//Add marker if queue not empty.
			if(!queue.isEmpty()) {
				queue.add(marker);
			}
			
			System.out.println(" ");
	}
	
			
	}

- nileshpatel7048 October 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.tree;

import java.util.ArrayDeque;
import java.util.Queue;

class PrintSameLevelTree {
	
	public static void main(String args[]) {
		com.TreeNode root = com.TreeNode.getTree1();
		printSameLevel(root);
	}
	

	public static void printSameLevel(com.TreeNode root){
	
	Queue<com.TreeNode> queue = new ArrayDeque<com.TreeNode>();
	
	com.TreeNode marker = new com.TreeNode("-1");
	queue.add(root);
	queue.add(marker);
	
	while(!queue.isEmpty()) {
		
			while(!queue.peek().data.equalsIgnoreCase("-1")) {
				com.TreeNode node = queue.poll();
				System.out.print(node + " ");
				if(node.left != null ) queue.add(node.left);
				if(node.right != null ) queue.add(node.right);	
			}
			
			queue.poll();
			
			if(!queue.isEmpty()) {
				queue.add(marker);
			}
			
			System.out.println(" ");
	}
	
			
	}


}

- nileshpatel7048 October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void allNodesAtSameDepth(ArrayList<LinkedList<TreeNode>> arr, TreeNode node,int level){
		//ArrayList<LinkedList<TreeNode>> arr = null;
		if(node == null){
			return ;
		}
		
		LinkedList<TreeNode> list = null;
		if(arr.size()==level){
			list = new LinkedList<TreeNode>();
			arr.add(list);
		}
		else{
			list = arr.get(level);
			//list.add(node);
		}
		list.add(node);
		allNodesAtSameDepth(arr,node.left, level+1);
		allNodesAtSameDepth(arr,node.right, level+1);
		
		//return arr;
	}
	public static ArrayList<LinkedList<TreeNode>> createList(TreeNode root){
		ArrayList<LinkedList<TreeNode>> arr = new ArrayList<LinkedList<TreeNode>>();
		allNodesAtSameDepth(arr, root, 0);
		return arr;
	}
	public static void main(String[] args) {
		TreeNode n = new TreeNode(16,null);
		  n.add(17, n);
		  n.add(18,n);
		n.add(12,n);
		  n.add(13,n);
		n.add(9,n);
		  n.add(10, n);
		n.add(7,n);
		// TODO Auto-generated method stub
		ArrayList<LinkedList<TreeNode>> arr = createList( n);
		
		for(LinkedList<TreeNode> list: arr){
			for(TreeNode node: list){
				System.out.println(node.data);
			}
		}
	}

- Resh January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void PrintBFS(Node root) {
	
	if (root == null) {
		return;
	}
	
	List<Node> curLevelNodes = new ArrayList<>();
	curLevelNodes.add(root);
	
	while (!curLevelNodes.isEmpty()) {
		List<Node> nextLevelNodes = new ArrayList<Node>();
		for (Node node : curLevelNodes) {
			System.out.print(String.valueOf(node.data) + ' ');
			if (node.left != null) {
				nextLevelNodes.add(node.left);
			}
			if (node.right != null) {
				nextLevelNodes.add(node.right);
			}
		}
		System.out.println();
		curLevelNodes.clear();
		curLevelNodes.addAll(nextLevelNodes);
	}

}

- pavel.kogan January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {
    struct Node *left, *right;
    int data;
};

void print_level_order(Node *tree)
{
    std::queue<Node*> q;

    q.push(tree);

    while (!q.isempty())
    {
        Node *current = q.front();
        q.pop_front();

        if (current)
        {
            printf ("%d ", current->data);

            q.push(NULL);

            if (q->left)
                q.push(q->left);

            if (q->right)
                q.push(q->right);
        }
        else
        {
            printf("\n");
        }
    }

    printf("\n");
}

- xyz March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would create a class that extends node with the ability to set depth. Then, go through normal BF iteration. At the end of each iteration, peek the queue and print a newline if the next node is deeper than the current node.

- Dave July 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not a recursive solution like this -

private node NewRoot = null;
public node reverse(node current) {
	if(current.left == null) {
		NewRoot = current; 
		return current;
	}
	
	node leftNode = reverse(current.left);
	leftNode.right = current; 
	leftNode.left = current.right;

}

- redi October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void levelOrder() {
Queue<Node> q = new LinkedList<Node>();

q.add(root);
int curlevel = 1;
int nextlevel = 0;

while(!q.isEmpty()) {

Node v = q.poll();

System.out.print(v.data + " ");

if(v.left != null) {
q.add(v.left);
++nextlevel;
}

if(v.right != null) {
q.add(v.right);
++nextlevel;
}

--curlevel;

if(curlevel == 0) {
curlevel = nextlevel;
nextlevel = 0;
System.out.println();
}

} // while

}
--
fahim-patel.blogspot.com

- fahi August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void levelOrder() { 
		Queue<Node> q = new LinkedList<Node>();
		
		q.add(root);
		int curlevel = 1;
		int nextlevel = 0;
		
		while(!q.isEmpty()) { 
			
			Node v = q.poll();
			
			System.out.print(v.data + "  ");
			
			if(v.left != null) {
				q.add(v.left);
				++nextlevel;
			}
			
			if(v.right != null) {
				q.add(v.right);
				++nextlevel;
			}
			
			--curlevel;
			
			if(curlevel == 0) { 
				curlevel = nextlevel;
				nextlevel = 0;
				System.out.println();
			}		
			
		} // while
		
	}

---
fahim-patel.blogspot.com/

- Anonymous August 18, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More