Amazon Interview Questions

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

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.

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;
         value = countLeafInBST(root->leftChild ) + countLeafInBST(root-> rightChild );

      return (value);

Leave a Reply

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

You are commenting using your 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