Microsoft Interview Question
Software Engineer / DevelopersI think question is very clear.It was asked in MS interview when it visited our campus last yr.We find the hight of a BST.Now the variation is, if leafs of that tree are connected to each other.so that from one leaf, we can go to next leaf... so for such tree, find the height of the node
OK. I C. since the right and left child has been occupied. The leaf node can't be determined as usual.
Solution: DFS, leaf node condition node->left->right == node || !node->left && !node->right || node->right == last visitleaf && !node->right
Is the last element in the DLL connect to the head? otherwise, third condition not need
If not,
i think .. current ->left->right = current.. if it holds gud then the current will be leaf.
this only is sufficient.
x is value of the node whose hight, we need to know
root is the root of the BST
int level ( node * root, int x)
{
static int level = 0;
if ( root == NULL)
{
level = -1;
return level ; }
else if ( root->val == x)
{ level = 0;
return level ; }
if( roo->left)
{
if ( root->left->right == root)
level = -1;
else
level = (root->left)? level(root->left) ;
if(root->right)
{
if ( root->left->right == root)
level = -1;
else
level = level( root->right);
}
What we know the answer for hight of tree has leaf node no link to other node, so This algo wont work in case of leaf node is pointing to other leaf node ,
So we need to explore new algo in this context(Leaf is poitnig to other leaf).
i think .. current ->left->right = current.. if it holds gud then the current will be leaf.
this only is sufficient.
x is value of the node whose hight, we need to know
root is the root of the BST
int level ( node * root, int x)
{
static int level = 0;
if ( root == NULL)
{
level = -1;
return level ; }
else if ( root->val == x)
{ level = 0;
return level ; }
if( roo->left)
{
if ( root->left->right == root)
level = -1;
else
level = (root->left)? level(root->left) ;
if(root->right)
{
if ( root->left->right == root)
level = -1;
else
level = level( root->right);
}
I guess we can use a trick here: when we reach a leaf node, even though its next node (left child or right child) is another leaf, the parent node of the next leaf node is not the current leaf node. By doing so, we know if it is a leaf node or not and the height can be identified easily.
guys, the height is logn, n - the number of leafs.
it's pretty clear that we can't use DFS or whatever because we're only supposed to use the LL!
if we divide by 2 untill we get 1 then we'll get the height.
actually we get a little more than the height.
this is only optimized if the tree is a full tree (each node has either no sons or 2 sons).
but it's a very good estimation no matter how you look at it (save O(n) that is :D)
???. Binary Search O(lg(n))?? I c no reason why doubly LL.
- T December 18, 2009Please clarify the questions.