Microsoft Interview Question
Software Engineer / DevelopersTeam: yammer
Country: United States
/* height of Binary tree iteratively */
private static Integer height(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
q.add(root);
q.add(new BinaryTreeNode(-1));
int level = 0;
while (!q.isEmpty()) {
temp = q.poll();
if (temp.getData() == -1) {
if (!q.isEmpty())
q.add(new BinaryTreeNode(-1));
level++;
} else {
if (temp.getLeft() != null)
q.add(temp.getLeft());
if (temp.getRight() != null)
q.add(temp.getRight());
}
}
return level;
}
height is usually defined as max depth of any node
h( Node x )
{
if( x == nil ) return 0; //tree rooted at nil has 0 height
//tree rooted here is 1+ height of tallest subtree
return max( h(x.left) , h(x.right) ) +1 ;
}
int getHeight(Node root){
if(root==null) return 0;
int L=0;
int R=0;
if(root.L!=null) L=1+getHeight(root.L);
if(root.R!=null) R=1+getHeight(root.R);
return max(L,R);
}
public class Max_height_tree {
int height1,height2;
public Max_height_tree() {
height1 = 0;
height2 =0;
}
public int height(TreeNode node)
{
if(node==null)
return -1;//This decides if a
else{
height1=height(node.leftchild)+1;
height2 =height(node.rightchild)+1;
}
return (Math.max(height1,height2));
}
}
Here I`ll post a non-recursive way.
int height(TreeNode * root){
if (!root) return 0;
stack<TreeNode *> s;
TreeNode * current = root;
int maxHeight = 0;
while(true){
if (current){
s.push(current);
current = (current->left != NULL)?current->left:current->right;
}
else{
maxHeight = s.size()>maxHeight?s.size():maxHeight;
current = s.top();
s.pop();
if (s.empty()) break;
if (current == s.top()->left){
current = s.top()->right;
}
else{
current = NULL;
}
}
}
return maxHeight;
}
public static int maxDepth;
public static void Width(Node tree)
{
var queue = new Queue<KeyValuePair<int, Node>>();
queue.Enqueue(new KeyValuePair<int, Node>(0, tree));
while (queue.Count > 0)
{
var node = queue.Dequeue();
var level = node.Key;
maxDepth = Math.Max(maxDepth, level);
foreach(var child in node.Value.Children)
queue.Enqueue(new KeyValuePair<int, Node>(level + 1, child));
}
}
- Vir Pratap Uttam May 04, 2015