Microsoft Interview Question
Software Engineer in TestsTeam: Windows Live
Country: United States
Initialize a depth variable to 1. Do a traversal from the root, incrementing the variable by 1 every time you go from a parent node to a child node and decrementing the variable by 1 every time you go from a child node to a parent node. Every time you increment the variable, check to see if it's greater than a maxDepth variable, and if so, update maxDepth.
Let OPT[i] = height at i th node in the tree
The recurrence relation would be
OPT[i] = Max{OPT[2i]+1, OPT[2i+1]+1}
so a iterative solution for above would be,
int depth(int *tree){
for(int i=1; i<n; i++){ //I am assuming my tree is in a array
if(2i < m && 2i+1 < n)
OPT[i] = 0; //If this is a leaf then height at that node is 0
}
for(int i=n; i>=1; i--){
OPT[i] = max(OPT[2i]+1, OPT[2i+1]+1);
}
return OPT[1]; //The root of the tree is at tree[i] and dept for that node is
// at OPT[1]
}
typedef std::pair<Node*,int> NodeLevelPair_t;
int getMaxDepth( Node* root )
{
int maxDepth = 0;
if ( root )
{
std::queue< NodeLevelPair_t > q;
q.push( NodeLevelPair_t( root , 1 ) );
while ( ! q.empty() )
{
NodeLevelPair_t curNode = q.front();
q.pop();
if ( curNode.second > maxDepth )
maxDepth = curNode.second;
if ( curNode.first->left != NULL )
q.push( NodeLevelPair_t( curNode.first->left , curNode.second + 1 ));
if ( curNode.first->left != NULL )
q.push( NodeLevelPair_t( curNode.first->left , curNode.second + 1 ));
}
}
return maxDepth;
}
Assuming Tree is a object Node* with left and right ptrs
int finddepth(Node root, int depth)
{
if(!root)
{
return depth;
}
int depthleft = finddepth(root->large,depth+1);
int depthright = finddepth(root->small,depth+1);
return (depthleft>depthright?depthleft:depthright);
}
int Height(Tree t) {
- cinderella October 29, 2011int height = -1;
if(t != NULL) {
std::list<Tree> q; //Queue to store tree nodes
q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level
while(!q.empty()) {
TreeNode *node = q.front();
q.pop_front();
if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty
height++;
if(!q.empty())
q.push_back(NULL);
}
else {
if(node->left)
q.push_back(node->left);
if(node->right)
q.push_back(node->right);
}
}
}
return height;
}