Page 202 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 12: Introduction to Trees

The binary tree appears as shown in the figure given below. Notes
Figure 12.2: Representation of Binary Tree

Source: http://datastructures.itgo.com/trees/concept.htm
As you can see, ‘leftchild’ and ‘rightchild’ are pointers to another tree-node. The “leafnode” will
have NULL values for these pointers.

12.2.1 Binary Tree Creation

The binary tree creation follows a very simple principle — for the new element to be added,
compare it with the current element in the tree. If its value is less than the current element in the
tree then move towards the left side of that element or else to its right. If there is no sub tree on
the left, make your new element as the left child of that current element or else compare it with
the existing left child and follow the same rule. Exactly same has to done for the case when your
new element is greater than the current element in the tree but this time with the right child.
The algorithm is given as below:

1. Step-1: If Value of New element < current element then go to step-2 or else step-3.
2. Step-2: If the Current element does not have a left sub-tree then make your new element
the left child of the current element; else make the existing left child as your current
element and go to step-1.
3. Step-3: If the current element does not have a right sub-tree then make your new element
the right child of the current element; else make the existing right child as your current
element and go to step-1.
C implementation is given as below.
struct NODE
{
struct NODE *left;
int value;
struct NODE *right;
}
create_tree(struct NODE *curr, struct NODE *new)
{
if(new->value <= curr->value)
{
if(curr->left != NULL)
create_tree(curr->left, new);
else
curr->left = new;

LOVELY PROFESSIONAL UNIVERSITY 195