Page 250 - DCAP407_DATA_STRUCTURE

Unit 13: Binary Search Trees

Did you know? The insertion, deletion and search operations have an average case complexity of
O(log n), where n is the number of nodes in the binary search tree.

Write a pseudocode for traversing a binary search tree recursively.

13.1.4 Other Operations
Finding the Height of a Tree
The maximum level is referred as the height of the tree. The root is always at zero level, the adjacent
nodes to the root are the first level, and so on. In the given figure 13.12, the height of the tree is 3. The
height of the tree is also referred as the depth of the tree.

Figure 13.12: Binary Tree

The C function to find the height of a tree is shown in the following example.

struct node
{
int element;
struct node *L;
struct node *R;
};
typedefstruct node* NODE;
int max(int x, int y) // function to find maximum of two numbers
{
return(x>y)?x:y;
}
int height(NODE root) // function to find the height of the tree
{
if(root==NULL)
return 0;
return 1+max(height(root->L),height(root->R));
}
In this example,

1. A structure named node is created. It consists of two pointer variables
named L and R that point to the left node and right node.

LOVELY PROFESSIONAL UNIVERSITY 243