Linkedin Interview Question
Country: United States
Interview Type: Phone Interview
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();
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);
}
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.
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.
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;
}
}
}
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();
}
}
}
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("");
}
}
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;
}
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(" ");
}
}
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(" ");
}
}
}
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);
}
}
}
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);
}
}
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");
}
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
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/
My answer
- PrateekS. July 29, 2014