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

insert(A,x):   

//If the tree is empty, return a new node
if (A == NULL) return newNode(x);
/* Otherwise, recur down the tree */

if (x < A->key)

A->left = insert(A->left, x);

else if (x > node->key)

A->right = insert(A->right, x);

/* return the (unchanged) node pointer */
return node;

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

int leaves(A,x):

if(A == NULL)      

    return 0;

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

    return 1;           

  else

    return leaves(node->left)+

           leaves(node->right);

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

Explanation of leaves(A,x):

Since this program is similar to traversal of tree, time and space complexities will be same as Tree traversal.i.e.O(n)

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

Explanation:insert(A,x)

This Algorithm would determine the position as per value of node to be added and new node would be added into binary tree.

Steps:
1)Check first if tree is empty, then insert node as root.

2) Check if node value to be inserted is lesser than root node value, then

Call insert() function recursively while there is non-NULL left node
3)Check if node value to be inserted is greater than root node value, then

Call insert() function recursively while there is non-NULL right node

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