Question

You are given a general search tree (not necessarily AVL tree). Formulate a function that prints out the n values of the search tree in ascending order. Determine the worst-case time and space complexities of your function.

Answer 1

If given a general search tree, and not an AVL tree, the inorder traversal will prints the n values of the search tree in ascending order. The function goes here:

inorder(Node *root)

{

if(root != NULL)

{

inorder(root->left);

print(root->info);

inorder(root->right);

}

}

The above traversal function will traverse the elements of the search tree in inorder.

But when the tree is severely skewed, that is, when the elements are inserted in ascending order, assume, 1, 2, 3, 4, 5 the tree looks as shown below:

In this case, the above given function will traverse this tree in O(n) time. This is the worst case efficiency of the binary search tree. Note that this happens only when the tree is not balanced. And the space complexity will be as usual, O(n), where n is the number of nodes.

If you have any further queries, just get back to me.