Amazon Interview Questions

How many  distinct binary search tree can be possible by given n node.

Explanation:
n=(0,1,2,3,4, 5) is (1,2,5,14,42) which is the Catalan number
Cn = 2n! / (n+1)! n!

Calculate the minimum number of nodes in AVL Tree with height h.

Explanation:
N(H) =  1               height h=0
N(H) =  2               height h=1
1+ N(H-1) + N(H-2)      height > 1

Find the number of leaf node in given binary tree.

struct CellNode { 
   struct CellNode * leftChild;
   int data;
   struct CellNode * rightChild;
};

countLeafInBST(strcut CellNode *root)
{
      static int value=0;
       if (!root)
          return  0;
       else if (root->leftChild == NULL && root-> rightChild == NULL)
          return 1;
       else
         value = countLeafInBST(root->leftChild ) + countLeafInBST(root-> rightChild );

      return (value);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s