Inscribe an algorithm that supports the following operations

Inscribe 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

Algorithm insert(A, x):
node = createNode(x);
if A == null:
A = node;
return;
else
if x < A->info:
if A->leftChild == null
A->leftChild = node;
return;
else
insert(A->leftChild, x);
else
if A->rightChild == null
A->rightChild = node;
return;
else
insert(A->rightChild, x);

Algorithm leaves(A, x):   
if A == null:
return 0;
else
return 1 + leaves(A->leftChild, x) + leaves(A->rightChild, x);