**BINARY SEARCH TREE**

C STRUCTURE TUTORIAL

PART 6

C STRUCTURE TUTORIAL

PART 6

**CONTENTS**

• I. INTRODUCTION

• II. BINARY SEARCH TREE

• III. INSERT ALGORITHM

• IV. ANALYSIS OF EXAMPLE PROGRAM

• V. EXAMPLE PROGRAM

• VI. REFERENCES

• I. INTRODUCTION

• II. BINARY SEARCH TREE

• III. INSERT ALGORITHM

• IV. ANALYSIS OF EXAMPLE PROGRAM

• V. EXAMPLE PROGRAM

• VI. REFERENCES

**I. INTRODUCTION**

Hello; nice to meet you. Welcome to the “Binary Search Tree - C Structure Tutorial - Part 6.”

**II. BINARY SEARCH TREE**

A tree is a nonlinear two-dimensional data structure whose nodes contain two or more pointer links.

A binary tree is a tree which contains nodes with two pointer links of which none, one, or both can be null.

A binary search tree is a binary tree whose nodes contain a left pointer link, a right pointer link, and one or more data elements of which one data element is a key field. Based on the key data element field, the left sub-tree key field data element values are less than the parent node key field value and the right sub-tree key field data element values are greater than or equal to the parent node key field value. The binary search tree is also a recursive hierarchical data structure and its shape depends on the order of insertion of the data elements. The binary search tree can be used for many purposes including inserting, searching, deleting, sorting and retrieving data.

**1. Root**

A binary search tree starts with a node called a root which is the topmost node in the tree. A root pointer points to the root and left and right pointers recursively point to smaller sub-trees to the bottom and on either side of the root.

The information represented by each node is a struct record, similar to that of a linked list.

**2. Parent, Children and Siblings**

Parent describes the root node.

Children describe the nodes to the bottom left or right of a parent. If a node has only one child, that child must be identified as either the left child or the right child.

Siblings are children of the same parent.

A parent node can have zero, one or a max of two children nodes. As we follow down the tree from a parent to a child the child becomes a parent and has children nodes of its own. However the rule still holds, and the new parent node can only have zero, one or a max of two child nodes.

**3. Ancestor and Descendent**

An ancestor of a given node is either the parent, the parent of the parent, the parent of that parent, etc. For example, in section III below 18 is an ancestor of 33; however, 66 is not an ancestor of 33.

The counterpart of ancestor is descendant. For example, in section III below 33 is a descendent of 18; however, 84 is not a descendent of 18.

**4. Balanced Binary Search Tree**

The goal, when creating a binary search tree is to have a balanced tree, with each parent node having the same number of children nodes to its bottom left and to its bottom right. In other words, each root-to-leaf path should have exactly the same number of nodes. Remember, you want a binary search tree and not a linked list where each node only has one bottom branch to one child node.

**5. Internal and External Nodes**

Internal nodes are nodes with two children.

External nodes have one or no children. As shown in section III below, an external node with a terminating branch with no children is represented as a NULL pointer from a parent node.

**6. Leaf**

A node that has neither a left child nor a right child is referred to as a leaf node. In our example in section III below, the leaf nodes are 12, 45, 84 and 33.

**III. INSERT ALGORITHM**

Given the following randomly selected eight integer numbers: 44, 66, 18, 84, 22, 12, 33, and 45; the data element value in the root node key field would be the first randomly selected number, i.e., 44.

...........................44

........................./....\

As shown above, the root is the first new node in the binary search tree. The root has two downward branches or links. The left branch leads to a sub-tree which only contains key field data element values less than the key field data element value of the root node. The right sub-tree only contains key field data element values greater than the key field data element value of the root node.

For example, our next random number is the integer 66. When we compare 66 to 44 we see 66 is greater than 44. Therefore, as shown below, 66 will become the data element value in a new node to the bottom right of the root node.

...........................44

........................./....\

................................66

............................../.....\

Selecting the next random number, which is the integer 18, and comparing 18 to the root, we see 18 is less than 44. Therefore, as shown below, 18 will become the data element value in a new node to the bottom left of the root; as shown below:

............................44

........................./.....\

......................18..........66

.................../.....\...../.....\

Selecting the next random number, which is the integer 84, and comparing 84 to the root 44, we see 84 is greater than 44. However, 66 is already in the node to the bottom right of the root 44. Therefore, 66 becomes the root. Comparing 84 to the new root 66, we see 84 is greater than 66. Therefore, as shown below, 84 becomes the data element value in a new node to the bottom right of the root 66.

............................44

........................./.....\

......................18..........66

.................../.....\...../.....\

........................................84

...................................../.....\

Selecting the next random number, which is the integer 22, and comparing 22 to the root 44, we see 22 is less than 44. However, 18 is already in the node to the bottom left of the root 44. Therefore, 18 becomes the new root. Comparing 22 to the root 18, we see 22 is greater than 18. Therefore, as shown below, 22 becomes the data element value in a new node to the bottom right of the root 18.

............................44

........................./.....\

......................18..........66

.................../.....\...../.....\

.........................22...........84

......................./.....\....../.....\

Selecting the next random number, which is the integer 12, and comparing 12 to the root 44, we see 12 is less than 44. However, 18 is already in the node to the bottom left of the root 44. Therefore, 18 becomes the new root. Comparing 12 to the root 18 we see 12 is less than 18. Therefore, as shown below, 12 becomes the data element value in a new node to the bottom left of the root 18.

............................44

........................./.....\

......................18..........66

.................../.....\......./.....\

.................12......22...........84

.............../.....\./.....\....../.....\

Selecting the next random number, which is the integer 33, and comparing 33 to the root 44, we see 33 is less than 44. However, 18 is already in the node to the bottom left of the root 44. Therefore, 18 becomes the new root. Comparing 33 to the root 18, we see 33 is greater than 18. However, 22 is already in the node to the bottom right of the root 18. Therefore, 22 becomes the new root. Comparing 33 to the root 22, we see 33 is greater then 22. Therefore, as shown below, 33 becomes the data element value in a new node to the bottom right of the root 22.

.............................44...

........................./..........\...

....................18..................66...

................/........\............./........\

..........12..............22....................84...

......./.....\.........../....\................../...\.

.....null...null....null...33..............null..null.

.............................../..\..............

............................null.null..................

Selecting the last random number, which is the integer 45, and comparing 45 to the root 44, we see 45 is greater than 44. However, 66 is already in the node to the bottom right of the root 44. Therefore, 66 becomes the new root. Comparing 45 to the root 66, we see 45 is less than 66. Therefore, as shown below, 45 becomes the data element value in a new node to the bottom left of the root 66.

Given our randomly selected eight numbers: 44, 66, 18, 84, 22, 12, 33, and 45; the completed binary search tree is as follows:

.............................44...

........................./..........\...

....................18..................66...

................/........\............./........\

..........12..............22........45..........84...

......./.....\.........../....\....../..\......../...\.

.....null...null....null...33..null..null..null..null.

.............................../..\..............

............................null.null..................

We end up with a binary search tree of size 8, depth 3, with root 44, and leaves 12, 45, 84 and 33. Notice the binary search tree is almost balanced; the root-to-leaf path is two for all but leaf 33, which has a root-to-leaf path of three.

**IV. ANALYSIS OF EXAMPLE PROGRAM**

The example program contains detailed documentation and should be easy to follow assuming you have a firm foundation in linked lists and pointers.

Instead of using a menu with a boring switch multiple-selection statement and case labels, I used the following exciting array of three function pointers:

void( *ptr2Fcn[3] )( void ) = { exitt, unsorted, bst };

I think function pointers are more fun. The function pointers work as shown below:

**1. void( *ptr2Fcn[0] )( void ) = { exitt };**

When the user types integer 0 at the menu prompt, and presses Enter, the program uses the first function pointer to call the exitt() function and the program exits.

**2. void( *ptr2Fcn[1] )( void ) = { unsorted };**

When the user types integer 1 at the menu prompt, and presses Enter, the program uses the second function pointer to call the unsorted() function and the program screen prints the unsorted array of preselected random integers.

**3. void( *ptr2Fcn[2] )( void ) = { bst };**

When the user types integer 2 at the menu prompt, and presses Enter, the program uses the third function pointer to call the bst() function which inserts the preselected random integers into the binary search tree; and screen prints the resulting binary search tree ascending sort of the preselected random integers.

If you have any questions, post them after the tutorial and I will post replies.

**V. EXAMPLE PROGRAM**

/* BINARY SEARCH TREE C STRUCTURE TUTORIAL PART 6 */ #include<ctype.h> /* Character Class Tests */ #include<stdio.h> /* Standard I/O. */ #include<stdlib.h> /* Utility Functions. */ /* DECLARATIONS */ /* Node structure containing an int value and left and right child pointers. */ struct childPtr { int value; struct childPtr *left; struct childPtr *right; }; typedef struct childPtr node; #define HEADER \ "\n\n BINARY SEARCH TREE\n" \ " C STRUCTURE TUTORIAL\n" \ " PART 6\n\n" \ " 0 EXIT\n" \ " 1 Display unsorted array of random integers.\n" \ " 2 Display Binary Search Tree ascending sort.\n\n" \ " Enter your menu selection of integer 0, 1, or 2 then press enter: " /* Declaration of an int array of size 8, initialized with eight random integer values. */ int A[ 8 ] = {44, 66, 18, 84, 22, 12, 33, 45}; const int SIZE_A = sizeof A / sizeof A[ 0 ]; /* Declaration of an int pointer array of size 8. */ int *selection[ 8 ]; int getInteger( int *maybe ) { char alpha, buff [ 80 ]; return fgets( buff, sizeof buff, stdin) && !isspace(*buff ) && sscanf( buff, "%d%c", maybe, &alpha) == 2 && (alpha == '\n' || alpha == '\0' ); } /* FUNCTION PROTOTYPES */ /* The three menu selection functions. */ void exitt( void ); void unsorted( void ); void bst( void ); /* Initialize int pointer array. */ void initialize( void ); /* Node insert function. */ void insert(node **subTree, node *element); /* Display function for binary search tree sorted in ascending order. */ void display( node *subTree ); int main( int argc, char* argv[] ) { /* Call initialize int pointer array function. */ initialize(); /* Initialize array of three pointers to functions, each with no arguments, and each returns void. */ void( *ptr2Fcn[3] )( void ) = { exitt, unsorted, bst }; printf( HEADER ); int menuSelection; do { fflush( stdout ); } while ( !getInteger(&menuSelection) ); while(( menuSelection >= 0) && ( menuSelection < 3 )) { /* Invoke the function at location menuSelection in the array ptr2Fcn. */ ( *ptr2Fcn[ menuSelection ] )(); printf( HEADER ); do { fflush( stdout ); } while ( !getInteger( &menuSelection ) ); } return 0; } /* FUNCTION DEFINITIONS */ /* Node insert function. */ void insert( node **subTree, node *element ) { if( !( *subTree ) ) { *subTree = element; return; } /* Insert new value in left node if lesser value than parent. Insert new value in right node if greater or equal value than parent. */ if( element->value < ( *subTree )->value ) insert( &( *subTree )->left, element ); else if( element->value >= ( *subTree )->value ) insert( &( *subTree )->right, element ); return; } /* Function definition for binary search tree sorted in ascending order. */ void display( node *subTree ) { if( subTree->left ) display( subTree->left ); printf(" %d\n", subTree->value ); if( subTree->right ) display( subTree->right ); return; } /* Initialize int pointer array. */ void initialize(void) { int i = 0; for( i = 0; ( i < SIZE_A ); i++ ) { selection[ i ] = &A[ i ]; }; return; } void exitt( void ) { exit( 0 ); return; } /* Display unsorted array of random integers. */ void unsorted( void ) { printf("\n\n ******************************************************************************\n\n"); int u = 0; printf(" UNSORTED LINEAR ONE-DIMENSIONAL ARRAY OF RANDOM INTEGERS:\n\n "); for( u = 0; u < SIZE_A; u++ ) printf("%d ", A[u] ); printf("\n 0 1 2 3 4 5 6 7 <= Binary search tree insertion sequence.\n"); printf("\n\n ******************************************************************************\n\n"); return; } /* Binary Search Tree (BST) function definition. */ void bst( void ) { node *temp; node *root; root = NULL; int i = 0; for( i = 0; i < SIZE_A; i++ ) { temp = malloc( sizeof( node )); if( temp == NULL ) { fprintf( stderr, "Error: malloc failed to allocate memory." ); exit( 1 ); }else { temp->left = NULL; /* Sets the left child of the child node to null. */ temp->right = NULL; /* Sets the right child of the child node to null. */ /* Load random int data into binary search tree. */ temp->value = *selection[ i ]; /* Call node insert function. */ insert( &root, temp ); } } printf("\n\n ******************************************************************************\n\n"); printf(" BINARY SEARCH TREE ASCENDING SORT:\n\n"); /* Call display function for binary search tree sorted in ascending order. */ display( root ); printf("\n\n ******************************************************************************\n\n"); return; }

**VI. REFERENCES**

The C Programming Language by Brian Kernighan and Dennis Ritchie (Englewood Cliffs, N.J.: Prentice-Hall, 1978).

The C Programming Language Second Edition by Brian Kernighan and Dennis Ritchie (Upper Saddle River, N.J.: Prentice-Hall PTR, 1988).