Page 109 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes the left, then 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, the 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. Though this logic is followed for the creation of a Binary tree, this logic is often suitable to
search for a key value in the binary tree.

Algorithm for the Implementation of a Binary Tree

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.

Task “If a binary tree is a complete binary tree, it can be represented using an array
capable of holding n elements where n is the number of nodes in a complete binary tree.”
Discuss.

Lab Exercise Program: Depicts the segment of code for the creation of a binary tree.
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;
}
else
{
if(curr->right != NULL)
create_tree(curr->right, new);
else

104 LOVELY PROFESSIONAL UNIVERSITY