Consider a binary search tree T with nodes containing the fo

Consider a binary search tree T with nodes containing the four fields key, left, right, p. and ht, where key is an integer, left, and right are pointers to the two subtrees, p is a pointer to the parent of the node, and ht is the height of the node (the maximum length of a path from this node to a leaf). Design an algorithm for a procedure insert (T, x) that inserts to a binary searches tree T a new node x (whose key is not in the tree yet), and updates lit fields accordingly. The function should work in O(h) time, where h is the length of the access path.

Solution

Algorithm is implemented in C:

struct node
{
int key;
struct node *left, *right;
};

//function to create a new BST node
struct node *new_Node(int item)
{
struct node *tem = (struct node *)malloc(sizeof(struct node));
tem->key = item;
tem->left = tem->right = NULL;
return tem;
}

/INSERT PROCEDURE

/* Given key in BST,function to insert a new node. */
struct node* insert(struct node* T, int x)
{
/* If tree is empty then return a new node */
if (T == NULL) return new_Node(x);

/* else, repeat down the tree */
if (x < T->x)
T->left = insert(T->left, x);
else if (key > node->key)
T->right = insert(T->right, x);   

return T;
}