Page 252 - DCAP407_DATA_STRUCTURE

Unit 13: Binary Search Trees

In a binary search tree, a node with minimum value is found by traversing and obtaining the extreme
left node of the tree. If there is no left sub-tree, then the root is returned as the node which holds the
item of the least value.
The C function to return the address of least item in binary search tree is shown in following example.

struct node
{
int element;
struct node *L;
struct node *R;
};
typedef struct node* NODE;
NODE minimum(NODE root)
{
NODE data;
if(root==NULL)
return root;
data=root;
while(data->L!=NULL)
data=data->L; // finds left most node in binary search tree
return data;
}
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.

2. An object called NODE is created to access the structure element.
3. The function minimum is defined which accepts the address of the root
node as the parameter.
4. In the function minimum():
(a) A variable data is declared as type NODE.

(b) If root is entered as NULL, then the function root is returned, else,
the value of root is assigned to the variable data.
(c) Using the while loop, the extreme left node in the tree is found and
its address is returned.

Count Nodes and Leaves in a Tree

We obtain the number of nodes in the tree by traversing the tree using any traversal technique and
incrementing the counter whenever a node is visited. The variable count is taken as a global variable
and it is initialized to zero. In the given example, inorder traversal is used to visit each node. The C
function to obtain the number of nodes in a tree is given in the following example.

static count = 0;
struct node
{
int element;
struct node *L;
struct node *R;
};
typedef struct node* NODE;
int count_node(NODE root)
{

LOVELY PROFESSIONAL UNIVERSITY 245