Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
@ chisingh , you are right... just rephrasing the logic
Keep 2 queues to keep track of levels
Do BFS
After each level update the max elements and swap currLevelQ and nextLevelQ so that you are always working on currentlevelQ
The code is buggy. You are not utilizing all the elements of currentLevel. Though, the approach is right.
why swap currentLevel and nextLevel in the end? currentLevel is going to be empty anyways...
Code in C:
#include <stdio.h>
#include <stddef.h>
typedef struct treeNode
{
int data;
struct treeNode *left;
struct treeNode *right;
int visited;
}treeNode;
struct queue{
struct queue *next;
treeNode *node;
};
typedef struct queue queue;
void PrintInorder(treeNode *node)
{
if(node==NULL)
return;
PrintInorder(node->left);
printf("%d ",node->data);
PrintInorder(node->right);
}
void enq(treeNode *node, queue **head_qq, queue **taill)
{
queue *head_q = *head_qq;
queue *tail = *taill;
if(head_q == NULL || tail == NULL) { /* q is empty */
struct queue *q = malloc(sizeof(struct queue));
q->next = NULL;
q->node = node;
*head_qq = q;
*taill = q;
} else {
struct queue *temp = head_q;
while(temp->next != NULL) {
temp = temp->next;
}
struct queue *q = malloc(sizeof(struct queue));
q->next = NULL;
q->node = node;
temp->next = q;
*head_qq = q;
}
}
treeNode * deq(queue **tail)
{
struct queue *temp = *tail;
*tail = (*tail)->next;
return temp->node;
}
int q_empty(queue *head_q, queue *tail)
{
if(head_q == NULL || tail == NULL)
return 1;
else
return 0;
}
int q_size(queue *tail)
{
queue *temp = tail;
int count = 0;
while(temp != NULL){
temp = temp->next;
count++;
}
return count;
}
/*DFS uses stack*/
void bfs(treeNode *node)
{
int max, curr_level, max_level;
max = curr_level = 1;
queue *head_q_first, *tail_first, *head_q_second, *tail_second;
head_q_first = tail_first = head_q_second = tail_second = NULL;
enq(node, &head_q_first, &tail_first);
while(!q_empty(head_q_first, tail_first)) { /*check if the queue is empty*/
/* pop the stack and mark it visited*/
node = deq(&tail_first);
node->visited = 1;
printf("%d\n", node->data);
/*check if it has any left or right node*/
/*if yes then push it on the queu */
if(node->left != NULL && node->left->visited != 1)
enq(node->left, &head_q_second, &tail_second);
if(node->right != NULL && node->right->visited != 1)
enq(node->right, &head_q_second, &tail_second);
if(q_empty(head_q_first, tail_first)) {
/* swap the queues */
queue *temp1;
queue *temp = head_q_first;
head_q_first = head_q_second;
head_q_second = temp;
temp1 = tail_first;
tail_first = tail_second;
tail_second = temp1;
curr_level++;
if(q_size(tail_first) > max) {
max = q_size(tail_first);
max_level = curr_level;
}
}
}
printf("max_level %d\n", max_level);
}
treeNode * Insert(treeNode *node,int data)
{
if(node==NULL)
{
treeNode *temp;
temp = (treeNode *)malloc(sizeof(treeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right,data);
}
else if(data < (node->data))
{
node->left = Insert(node->left,data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
}
int main()
{
treeNode *root = NULL;
treeNode *temp;
queue *head_q, *tail;
head_q = tail = NULL; /*empty queue */
root = Insert(root, 13);
root = Insert(root, 9);
root = Insert(root, 16);
root = Insert(root, 5);
root = Insert(root, 12);
root = Insert(root, 19);
PrintInorder(root);
printf("\n");
bfs(root);
}
private int maxlevel() {
int lvl[] = new int[10];
maxNodesLevel(root, 0, lvl);
int max = 0;
int maxLevel = 0;
for (int i = 0; i < lvl.length; i++) {
if (max < lvl[i]) {
max = lvl[i];
maxLevel = i;
}
}
return maxLevel;
}
Global variable MAX;
find the hight;
for level=0 to i< height
int NumberofNodeAtLevelL(tree, level)
{
if (tree == NULL)
return 0;
if(level ==0 & Tree != NULL)
return 1;
l = NumberofNodeAtLevelL(tree->left, level-1)
r= NumberofNodeAtLevelL(tree->right, level-1)
MAX > (l+r) ? MAX : MAX = l+r;
return l+r;
}
}
will this solution not work??
how about this: if we can change the tree, its quite easy I guess. In the first traversal every node.value gets value 1 more than its parent. Second traversal we sum how many times each value occurs:
consider tree structure: value, right, left
step 1: traverse(by changing)
step 2 : count occurrences of same level
public static void traverse(node root)
{
if(root ==null)return;
if(root.left!=null) root.left.value = root.value+1;
if(root.right!=null) root.right.value = root.value+1;
traverse(root.right);
traverse(root.left);
}
arraylist<integer> arr = new arraylist<integer>
public void countmax(node root, arraylist<integer> arr)
{
if(root ==null)return;
arr[root.value]++;
countmax(root.left);
countmax(root.right);
}
finally return index of max of arr
i think something is missing from the question....??????????????
Given a binary tree return the level with maximum number of nodes i think it should return alway 1..
please correct me.????????????
In the above example level 1 has only one node where as level 3 has 4 nodes so the it should return 3. Since level 3 has max number of nodes it should return 3. For example lets say
1
/ \
2 3
/ \
4 5
/ \ / \
6 7 8 9
/ \
10 11
here level 4 has max no of nodes.So the answer is 4
//============================================================================
// Name : levelFind.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include<math.h>
using namespace std;
int findLevelWidth(int arr[], int sz, int lvl) {
cout << "Level " << lvl <<": ";
int width=0;
for (int i = ((1<<lvl)-1); i < ((1<<(lvl+1))-1);i++)
{
if(i==sz) break;
if(arr[i] > 0) { width++;}
cout << arr[i] << ",";
}
cout << endl;
return width;
}
int main() {
cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};
int size = sizeof(arr)/sizeof(arr[0]);
int lvlWdt=0;
for(int i = 0; i < log2(size); i++) {
int width = findLevelWidth(arr,size, i);
if (width > lvlWdt) { lvlWdt = width;}
}
cout << "Max width is in level: " << lvlWdt << endl;
return 0;
}
I think below algorithm should do -
1. Run a BFS, starting from root node.
2. Keep track of levels and no. of nodes in each level.
3. Update max_nodes_in_level and level_number, with no. of nodes in current level and current level number, IF no.of nodesin current level > max_nodes_in_level.
4. Return level_number.
int LevelwithMaxNumNodes(struct Node *node)
{
if(!node)
return 0;
map<int,int> mymap;
map<int,int> :: iterator it;
int level=0;
queue<struct Node *> myqueue;
myqueue.push(node);
myqueue.push(NULL);
while(!myqueue.empty())
{
struct Node *current=myqueue.front();
myqueue.pop();
if(current!=NULL)
{
it=mymap.find(level);
if(it==mymap.end())
mymap.insert(pair<int,int>(level,1));
else
{
int count=it->second;
mymap.erase(level);
mymap.insert(pair<int,int>(level,++count));
}
if(current->left)
myqueue.push(current->left);
if(current->right)
myqueue.push(current->right);
}
else
{
if(!myqueue.empty())
{
level++;
myqueue.push(NULL);
}
else
break;
}
}
int max=-1,count=-1;
while(!mymap.empty())
{
if(mymap.begin()->second>=count)
{
count=mymap.begin()->second;
max=mymap.begin()->first;
}
mymap.erase(mymap.begin());
}
return max;
}
private static int getLevel(NodeT root) {
int h = getHeight(root);
int []level = new int[h];
getLevel(root,level,1);
int max = level[0];
int iMax = 0;
for(int i = 1;i<h;i++){
if(max <level[i]){
max = level[i];
iMax = i;
}
}
return iMax+1;
}
private static void getLevel(NodeT node, int[] level, int i) {
if(node == null)
return;
else{
level[i-1]++;
getLevel(node.left,level,i+1);
getLevel(node.right,level,i+1);
}
}
private static int getHeight(NodeT root) {
if(root == null)
return 0;
else
return 1+Math.max(getHeight(root.left),getHeight(root.right));
}
public int MaxLevel(Node root){
if(root==null)
return -1;
//search the entire tree level by level
Queue<Node> cur = new Queue<Node>();
cur.offer(root);
int max = 0;
while((int size = cur.size())!=0){
max = size>max?size:max;
Queue<Node> parent = cur;
cur = new Queue<Node>();
while(parent.peek()!=null){
Node temp = parent.poll();
if(temp.left!=null)
cur.offer(temp.left);
if(temp.right!=null)
cur.offer(temp.right);
}
}
return max;
}
//recursion
public int getDepth(Node root){
if(root==null)
return 0;
else return max(getDepth(root->left), getDepth(root->right))+1;
}
public void getLevelInfo(Node root, int[] levelcount, int level){
if(root==null)
return;
levelcount[level]++;
getlevelInfo(root->left, levelcount, level++);
getlevelInfo(root->right, levelcount, level++);
return;
}
public int findMax(int[] array){
int max = INT_MIN;
for(int i=0;i<array.length;i++)
max = array[i]>max?arry[i]:max;
return max;
}
public int main(Node root){
int[] levelcount = new int[getDepth(root)];
getLevelInfo(root,levelcount,0);
print(findMax(levelcount));
return 0;
}
public static int levelWithMaxNodes(Node root) {
return levelWithMaxNodes(root, 0, new HashMap<Integer, Integer>(), 0);
}
private static int levelWithMaxNodes(Node root, int level, HashMap<Integer, Integer> map,
int maxLevel) {
if(root == null)
return 0;
Integer value = map.get(level);
if(value == null) {
map.put(level, 1);
}
else {
if(value > maxLevel) {
maxLevel = value;
}
map.put(level, value + 1);
}
if(root.getLeft() != null) {
maxLevel = levelWithMaxNodes(root.left, level + 1, map, maxLevel);
}
if(root.getRight() != null) {
maxLevel = levelWithMaxNodes(root.right, level + 1, map, maxLevel);
}
return maxLevel;
}
for(int i =1;i<=height(root); i++)
{
int nodes = getcountnodes(root,i);
if( nodes > max)
{
max = nodes;
max_level = i;
}
}
int getcountnodes(node * node , int level)
{if(node == NULL)
return 0;
if(level == 1)
{
return 1;
}
else
if (level > 1)
{
return getcountnode(root->left,leve-1) + getcountnodes(root->right,level-1);
}
}
We have to return level with maximum number of node. In other words we have to find width of the tree. Traverse the tree in pre-order fashion.
int getMax(int count[], int n)
{
int max = arr[0];
int i;
for (i = 0; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
int getMaxWidthRecur(struct node* root, count, level)
{
if(root == NULL)
{
return 0;
}
count[level]++;
getMaxWidthRecur(root->left, count, level + 1);
getMaxWidthRecur(root->right, count, level + 1);
}
int getMaxWidth(struct node* root)
{
int height = getHeight(root);
int* count = (int *) calloc(sizeof(int), height);
int level = 0;
getMaxWidthRecur(root, count, level);
return getMax(count, height);
}
int
maxLevel(TreeNode const *node)
{
if (node == NULL) return 0;
int maxLevelNodes = 0;
int currLevelNodes = 1;
int nextLevelNodes = 0;
int currLevelNotNULL = 1;
int nextLevelNotNULL = 0;
deque<TreeNode const *> queue;
queue.push_back(node);
while (!queue.empty()) {
TreeNode const *curr_node = queue.front();
queue.pop_front();
currLevelNodes -= 1;
if (curr_node != NULL) {
queue.push_back(curr_node->left_);
queue.push_back(curr_node->right_);
nextLevelNodes += 2;
if (curr_node->left_ != NULL) nextLevelNotNULL += 1;
if (curr_node->right_ != NULL) nextLevelNotNULL += 1;
}
if (currLevelNodes == 0 && nextLevelNodes > 0) {
// end of current level
if (currLevelNotNULL > maxLevelNodes)
maxLevelNodes = currLevelNotNULL;
currLevelNotNULL = nextLevelNotNULL;
nextLevelNotNULL = 0;
currLevelNodes = nextLevelNodes;
nextLevelNodes = 0;
}
}
return maxLevelNodes;
}
public void MaxNodesLevel(BNode root)
{
Queue<BNode> Currentqueue = new Queue<BNode>();
Queue<BNode> NextlevelQueue;
BNode temp;
int MaxNodeslevel = 0;
int prevLevelCount_Nodes = 0;
int MaxNodes = 0;
int CurrentlevelCount_Nodes = 0;
Currentqueue.queueNode(root);
while (!Currentqueue.empty())
{
NextlevelQueue = new Queue<BNode>();
while ((temp = Currentqueue.dequeNode()) != null)
{
if (temp.LChild != null) {
NextlevelQueue.queueNode(temp.LChild);
}
if (temp.RChild != null) {
NextlevelQueue.queueNode(temp.RChild);
}
}
CurrentlevelCount_Nodes = NextlevelQueue.size();
MaxNodes = prevLevelCount_Nodes > CurrentlevelCount_Nodes ? prevLevelCount_Nodes: CurrentlevelCount_Nodes;
prevLevelCount_Nodes = MaxNodes;
MaxNodeslevel += (MaxNodes == CurrentlevelCount_Nodes) ? 1 : 0;
Currentqueue = NextlevelQueue;
}
System.out.println("Level with highest(" + MaxNodes + ") nodes="+ MaxNodeslevel);
}
Algorithm:
I used BFS
Build a tree and supply the root node to the method.
Let me know if any case fails :)
public static void levelNodes(BinaryTreeNode root) {
Queue main = new ConcurrentLinkedQueue();
Queue childs = new ConcurrentLinkedQueue();
int max = 0;
int newMax = 0;
main.add(root);
max = 0;
do {
while (main.size() > 0 && main.element() != null) {
BinaryTreeNode node = (BinaryTreeNode) main.remove();
if (node.getLeft() != null) {
childs.add(node.getLeft());
newMax++;
}
if (node.getRight() != null) {
childs.add(node.getRight());
newMax++;
}
if (main.size() == 0 && childs.size() > 0) {
System.out.println();
main.addAll(childs);
childs.removeAll(childs);
if (newMax > max) {
max = newMax;
newMax = 0;
}
}
}
} while (main.size() > 0);
System.out.println("Max number of nodes in a level:" + max);
}
Perfect solution
import java.util.LinkedList;
import java.util.Queue;
public class BinarySearchTree {
TreeNode root;
class TreeNode {
double value;
TreeNode left;
TreeNode right;
public TreeNode(double value) {
super();
this.value = value;
left = null;
right = null;
};
}
public void insert(double value) {
root = insertT(root, value);
}
public TreeNode insertT(TreeNode root, double value) {
if (root == null) {
TreeNode r = new TreeNode(value);
return r;
}
if (value > root.value) {
// right
root.right = insertT(root.right, value);
} else if (value < root.value) {
root.left = insertT(root.left, value);
}
return root;
}
public void inorder() {
inorderT(root);
System.out.println();
}
private void inorderT(TreeNode root) {
if (root == null) {
return;
}
inorderT(root.left);
System.out.print(root.value + "\t");
inorderT(root.right);
}
public int MaxLevel() {
return MaxlevelT(root);
}
private int MaxlevelT(TreeNode root) {
int maxLevel = 0;
if (root == null) {
return maxLevel;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Queue<TreeNode> slave = new LinkedList<TreeNode>();
maxLevel = 1;
queue.offer(root);
while (!queue.isEmpty()) {
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
slave.offer(node);
}
if (slave.size() > maxLevel) {
maxLevel = slave.size();
}
while (!slave.isEmpty()) {
TreeNode node = slave.poll();
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
return maxLevel;
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(5);
bst.insert(4);
bst.insert(2);
bst.insert(6);
bst.insert(3);
bst.insert(1);
bst.insert(7);
bst.insert(8);
bst.insert(4.5);
bst.insert(5.5);
bst.inorder();
System.out.println(bst.MaxLevel());
}
}
we can use Level order to scan the tree, and update 2 counters, 1 for current level and the second is for the next level.
in each push into the queue do:
if node level == current level+1 -> counter2 ++
if node level != current level+1 -> store the Max between counter1 & counter2 , swap between them ' end initialize counter2 to 0.
when pushing is over return the max.
i'm using the fact that in the queue there at most 2 levels...
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
width = getWidth(tree, i);
if(width > maxWdth)
maxWdth = width
return width
/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1;
else if level greater than 1, then
return getWidth(tree->left, level-1) +
getWidth(tree->right, level-1);
your code will find the max width not the level. to find the level with max check this:
public int getMaxWidth(ref TreeNode tree){
int maxWdth = 0;
int width = 0;
int mxlevel = 0;
int level = 0;
//for (int i = 0; i < height(tree); i++)
for (int i = 1; i <= heightOfBinaryTree(ref tree); i++)
{
width = getWidth(ref tree, i);
level = i;
if (width > maxWdth)
{
maxWdth = width;
mxlevel = level;
}
}
//return maxWdth;
return mxlevel;
}
Def maxNodesLevel(root):
If root == null:
return 0
Q = Queue()
curLevelCount = 1
nextLevelCount = 0
Q.enqueue(root)
While not Q.empty():
V = Q.deque()
For n in V.getNeighbors():
nextLevelCount += 1
curLevelCount -= 1
if curLevelCount == 0:
curLevelCount = nextLevelCount
nextLevelCount = 0
return nextLevelCount
int levelWithMostNodes(TreeNode *node)
{
int currentLevel = 0;
int levelMostNodes = 0;
int maxNodes = 0;
int nodeCount = 0;
if(node == nullptr)
{
return 0;
}
queue<TreeNode*> nodeQueue;
queue<TreeNode*> children;
nodeQueue.push(node);
do {
do
{
TreeNode* node = nodeQueue.front();
if(node->leftChild != nullptr)
{
children.push(node->leftChild);
}
if(node->rightChild != nullptr)
{
children.push(node->rightChild);
}
nodeQueue.pop();
nodeCount += 1;
} while (!nodeQueue.empty());
if( nodeCount > maxNodes )
{
levelMostNodes = currentLevel;
maxNodes = nodeCount;
}
currentLevel++;
while (!children.empty())
{
nodeQueue.push(children.front());
children.pop();
}
nodeCount = 0;
} while (!nodeQueue.empty());
return levelMostNodes;
}
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
public class ModifiedBFS {
Queue<BinaryTreeNode> q;
public int method(BinaryTreeNode root)
{
ArrayList<Integer> l = new ArrayList<Integer>();
//int[] count = new count[];
q.add(root);
int level =0;
int intems = 1;
l.add(level, intems);
while(q.isEmpty() != true)
{
BinaryTreeNode p = q.remove();
level++;
if(p.left != null)
{
q.add(p.left);
intems++;
}
if(p.right != null)
{
q.add(p.right);
intems++;
}
l.add(level, intems);
}
Integer max = l.get(0);
for(int i=0; i<level ;i++ )
{
if(max.compareTo(l.get(i)) <0)
{
max = l.get(i);
}
}
return l.indexOf(max);
}
}
Keep track of levels using a marker.
public int mostDenseLevel() {
if(root == null) {
return -1;
}
Queue<Node> nodeQueue = new LinkedList<Node>();
int maxLevel = -1;
int maxCount = 0;
int curLevel = 0;
int curCount = 0;
Node marker = new Node(-1);
nodeQueue.add(root);
nodeQueue.add(marker);
while(!nodeQueue.isEmpty()) {
Node curr = nodeQueue.remove();
if(curr == marker) { // End of curr level reached
if(curCount > maxCount) {
maxCount = curCount;
maxLevel = curLevel;
}
if(!nodeQueue.isEmpty()) {
nodeQueue.add(marker);
}
curLevel++;
curCount = 0;
continue;
}
if(curr.left != null) {
nodeQueue.add(curr.left);
}
if(curr.right != null) {
nodeQueue.add(curr.right);
}
curCount++;
}
return maxLevel;
}
int LevelWithMaxNodes(Node* root)
{
if(!root)
return -1;
int maxNodes = 1;
int runningMaxNodes = 1;
int level = 1;
int runningLevel = 1;
Queue<Node*> myQ = new Queue();
Node* DELIMITER = null;
myQ.push(root);
myQ.push(DELIMITER);
while(!myQ.IsEmpty())
{
Node* current = myQ.dequeue();
if(current)
{
++runningMaxNodes;
// The below condition returns the first Level with max nodes, >= will give the last level with maxNodes
if(runningMaxNodes > maxNodes)
{
maxNodes = runningMaxNodes;
level = runningLevel;
}
if(current->left)
myQ.enqueue(current->left);
if(current->right)
myQ.enqueue(current->right);
}
else if(current == DELIMITER)
{
++runningLevel;
myQ.enqueue(DELIMITER);
}
}
return level;
}
We can do BFS and at the time of enqueuing a node
check if node number i.e. index of node is between 2^i (inclusive) and 2^i+1 (excluding) then do a count[i] ++;
note : here count is array which contains no of nodes of each level .
also root node is at level 0 and further levels are numbered accordingly ...
Easy solution:
int GetMaxNodeCountLevel(PBTree tree)
{
int level = -1;
CQueue<PBTree> queue;
int maxCount = -1;
int currentCount = -1;
int currentLevel = -1;
if (tree)
{
level = 0;
maxCount = 0;
currentCount = 0;
queue.Enqueue(tree);
while (!queue.IsEmpty())
{
queue.Enqueue(NULL);
currentLevel++;
currentCount = 0;
while (queue.GetHeadData() != NULL)
{
tree = queue.Dequeue();
currentCount++;
if (tree->Left)
{
queue.Enqueue(tree->Left);
}
if (tree->Right)
{
queue.Enqueue(tree->Right);
}
}
if (currentCount > maxCount)
{
maxCount = currentCount;
level = currentLevel;
}
tree = queue.Dequeue();
}
}
return level;
}
done recursively
int getHeight(Node *root){
if (root == NULL) return 0;
if (root->left != NULL) return getHeight(root->left) + 1;
if (root->right != NULL) return getHeight(root->right) + 1;
return 1;
}
int levelUtil(Node *root, int level){
if (root == NULL) return 0;
if (level == 1) return 1;
else{
return levelUtil(root->left, level-1) + levelUtil(root->right, level-1);
}
}
int maxLevel(Node *root){
int h = getHeight(root);
int maxLevel = 0; int maxCount = 0;
for (int i = 1; i<=h; i++){
int tmpCount = levelUtil(root, i);
cout << i << ": " << tmpCount << "\n";
if(tmpCount > maxCount) maxLevel = i;
}
return maxLevel;
}
- chisingh February 07, 2013int maxLevel(node *root) { int max, curr_level, max_level; if (root == NULL) return 0; queue<node *> currentLevel, nextLevel; currentLevel.push(root); max = curr_level = 1; while (!currentLevel.empty()) { node *curr = currentLevel.front(); currentLevel.pop(); if (curr->left != NULL) nextLevel.push(curr->left); if (curr->right != NULL) nextLevel.push(curr->right); if (currentLevel.empty()) { queue<node *> temp = currentLevel; currentLevel = nextLevel; nextLevel = temp; curr_level ++; if (currentLevel.size() > max) { max = currentLevel.size(); max_level = curr_level; } } } return max_level; }