<< Previous Article

A tree is one of the many data structures, which is naturally recursive, i.e. recursive by its design itself. A tree is made up of a so called “root” node, which has zero or more (sub)trees hanging from it, and each node would have some data &/or attributes associated with it. The subtrees give the natural recursion of lower order. And because of that, all the operations on a tree, starting from creation, can be done recursively.

A good example to understand this notion of recursion in trees is a (integer) binary search tree (BST). A (integer) binary tree is a tree with all its nodes having a maximum of two subtrees hanging from them(, and containing integer data). It would become a binary search tree, if data among all its nodes is unique, and the following conditions are satisfied for every node:

• Every data in the node’s left subtree (if any) is smaller than node’s data
• Every data in the node’s right subtree (if any) is greater than node’s data

The advantage of such a construction is that once the tree is created from say N given data points, searching for a specific data point, in those N data points, is very optimal – takes only log2(N) steps on an average. And that’s where the name binary “search” tree also comes from. And interestingly enough, if the tree is traversed in an inorder way, i.e. in the order of left subtree (if any), node itself, and then right subtree (if any), the data so obtained would be in the ascending sorted order.

Let B denote the binary search tree, and v any data value. Also, let B->left, B->data, B->right be the left subtree, data of the root node, right subtree, respectively of the binary search tree B. Then, the various operations of the binary search tree may be depicted recursively by recursing on the left & right subtrees, and with the actual operation in the terminating condition.

Inserting a value v in the BST B:

bst_insert(B, v) // only if v is not already there in B
{
	if (isempty(B))
	{
		setup(B); // With empty B->left and B->right
		B->data = v;
	}
	else if (v < B->data)
	{
		bst_insert(B->left, v);
	}
	else if (v > B->data)
	{
		bst_insert(B->right, v);
	}
}

Searching a value v in the BST B:

bst_search(B, v)
{
	if (isempty(B))
	{
		return false;
	}
	else if (v == B->data)
	{
		return true;
	}
	else if (v < B->data)
	{
		return bst_search(B->left, v);
	}
	else if (v > B->data)
	{
		return bst_search(B->right, v);
	}
}

Inorder Traversing the BST B:

bst_inorder(B)
{
	if (!isempty(B))
	{
		bst_inorder(B->left);
		print(B->data);
		bst_inorder(B->right);
	}
}

In case of deleting a node with a given value v from the BST B, it can again be done recursively, just that the actual deleting the node in the terminating condition, need to take care of the BST properties being maintained even after the delete. It may be depicted as follows:

Deleting the node with value v in the BST B:

bst_delete(B, v)
{
	if (!isempty(B))
	{
		if (v == B->data)
		{
			if (isempty(B->right))
			// Just connect the left subtree here
			{
				t = B;
				B = B->left;
				cleanup(t);
			}
			else if (isempty(B->left))
			// Just connect the right subtree here
			{
				t = B;
				B = B->right;
				cleanup(t);
			}
			else
			// Both subtrees are present
			// Replace by the biggest from the left subtree
			{
				B->data = get_n_delete_biggest(B->left);
			}
		}
		else if (v < B->data)
		{
			bst_delete(B->left, v);
		}
		else if (v > B->data)
		{
			bst_delete(B->right, v);
		}
	}
}

And the get_n_delete_biggest(B), used above, may be implemented (again recursively) as follows:

get_n_delete_biggest(B) // B is assumed to be never empty
{
	if (isempty(B->right))
	// "root" node itself is the biggest
	// Replace by the left subtree
	{
		v = B->data;
		t = B;
		B = B->left;
		cleanup(t);
	}
	else
	{
		v = get_n_delete_biggest(B->right);
	}
	return v;
}

Next Article >>