Describe an algorithm that supports the following operations

Describe an algorithm that supports the following operations on a binary search tree, whose nodes have distinct integer keys:

• insert(A, x) - insert a node with key x into a set A (you may assume that no node in A has key x

• leaves(A, x) - return the number of leaves in the subtree of A rooted in the node with the key x (return null if no node in the tree has key x)

Explain the idea behind your approach. Both operations should run in time O(h), where h is the height of T. Show that your algorithm achieves the bound.

Solution

=======================================

int Leaves(A,x)

{

  if(A == NULL)      

    return 0;

  if(A->left == NULL && A->right==NULL && A->data ==x)     

    return 1;           

  else

    return getLeafCount(A->left)+

           getLeafCount(A->right);     

}

==============================================

Insert Algorithm:

In first,it will recursively insert in BST according to

1)First if root is empty,then it creates root as new node

2)if x<A,then insert x to left

3)if x>A,then insert x to right

Time complexity O(h)

In the worst-case, yes. A randomly-built BST with n nodes has a 2^n-1 / n! chance of being built degenerately, which is extremely rare as n gets to any reasonable size but still possible. In that case, a lookup might take (n) time because the search might need to descend all the way down to the deepest leaf.On expectation, though, the tree height will be (log n), so lookups will take expected O(log n)=O(h) time

==========================================================

Algorithm 2:Leaves

As code is similar to traversal of tree hence it is O(h).

T(n) = T(k) + T(n – k – 1) + c

Where k is the number of nodes on one side of root and n-k-1 on the other side.

k is 0 in this case.
T(n) = T(0) + T(n-1) + c
T(n) = 2T(0) + T(n-2) + 2c
T(n) = 3T(0) + T(n-3) + 3c
T(n) = 4T(0) + T(n-4) + 4c

T(n) = (n-1)T(0) + T(1) + (n-1)c
T(n) = nT(0) + (n)c

Value of T(0) will be some constant say d. (traversing a empty tree will take some constants time)

T(n) = n(c+d)
T(n) = O(n) (Theta of n)

=====================================================================