Binary Trees

A tree with only two child nodes for each parent node is called a Binary tree. A few terminologies used for a binary tree are:

  • A full binary tree is a binary tree in which each node has exactly zero or two children.
  • A perfect binary tree is a full binary tree in which all leaves have the same depth or same level.
  • A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

A complete binary tree is very special tree, it provides the best possible ratio between the number of nodes and the height. The height h of a complete binary tree with N nodes is at most O(log N).

We can easily prove this by counting nodes on each level, starting with the root, assuming that each level has the maximum number of nodes:
n = 1 + 2 + 4 + ... + 2h-1 + 2h
= 2h+1 - 1

Solving this with respect to h, we obtain
h = O(log n)
where the big-O notation hides some superfluous details.

Traversals

A traversal is a process that visits all the nodes in the binary tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds

      • depth-first traversal
      • breadth-first traversal

There are three different types of depth-first traversals, :

      • PreOrder(VLR) traversal – visit the parent first(V) and then left(L) and right children(R);
      • InOrder(LVR) traversal – visit the left child(L), then the parent(V) and the right child(R);
      • PostOrder(LRV) traversal – visit left child(L), then the right child(R) and then the parent(V);

There is only one kind of breadth-first traversal–the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.

As an example consider the following tree and its four traversals: PreOrder – 8, 5, 9, 7, 1, 12, 2, 4, 11, 3
InOrder – 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
PostOrder – 9, 1, 2, 12, 7, 5, 3, 11, 4, 8
LevelOrder – 8, 5, 4, 9, 7, 11, 1, 12, 3, 2
 

In the next picture we demonstrate the order of node visitation. Number 1 denote the first node in a particular traversal and 7 denote the last node.

undefined

Implementation of Traversals

These common traversals can be represented as a single algorithm by assuming that we visit each node three times. An Euler tour is a walk around the binary tree where each edge is treated as a wall, which you cannot cross. In this walk each node will be visited either on the left, or under the below, or on the right. The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit nodes from the below, we get an inorder traversal. And when we visit nodes on the right, we get a postorder traversal.


Binary Search Trees

We consider a particular kind of a binary tree called a Binary Search Tree (BST). The basic idea behind this data structure is to have such a storing repository that provides the efficient way of data sorting, searching and retrieving.

A BST is a binary tree where nodes are ordered in the following way:each node contains one key (also known as data)

      • the keys in the left subtree are less then the key in its parent node, in short L < P;
      • the keys in the right subtree are greater the key in its parent node, in short P < R;
      • duplicate keys are not allowed.

In the following tree all nodes in the left subtree of 10 have keys < 10 while all nodes in the right subtree > 10. Because both the left and right subtrees of a BST are again search trees; the above definition is recursively applied to all internal nodes: pix03

Operations on a BST

Insertion

The insertion procedure is quite similar to searching. We start at the root and recursively go down the tree searching for a location in a BST to insert a new node. If the element to be inserted is already in the tree, we are done (we do not insert duplicates). The new node will always replace a NULL reference.

Example 1: Given a sequence of numbers: 11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31. Draw a binary search tree by inserting the above numbers from left to right.

Searching

Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for. If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise – to the right child. The recursive structure of a BST yields a recursive algorithm.

Searching in a BST has O(h) worst-case run time complexity, where h is the height of the tree. Since s binary search tree with n nodes has a minimum of O(log n) levels, it takes at least O(log n) comparisons to find a particular node. Unfortunately, a binary search tree can degenerate to a linked list, reducing the search time to O(n).

Deletion

Deletion is somewhat more tricky than insertion. There are several cases to consider. A node to be deleted

      • is not in a tree;
      • is a leaf;
      • has only one child;
      • has two children.

If node is not in the tree, there is nothing to delete. If the node has only one child the procedure of deletion is identical to deleting a node from a linked list – we just bypass that node being deleted

Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two subtrees and therefore, some children of the internal node won’t be accessible after deletion. In the picture below we delete 8:

Deletion starategy is the following: replace the node being deleted with the largest node in the left subtree and then delete that largest node. By symmetry, the node being deleted can be swapped with the smallest node is the right subtree.

Example: In example 1, if we delete the node with data “11” then it results in either of the BSTs.

Implementation

#include<stdio.h>
#include<stdlib.h>

struct treeNode
{
        int data;
        struct treeNode *left;
        struct treeNode *right;
};

treeNode* FindMin(treeNode *node)
{
        if(node==NULL)
        {
                /* There is no element in the tree */
                return NULL;
        }
        if(node->left) /* Go to the left sub tree to find the min element */
                return FindMin(node->left);
        else 
                return node;
}
treeNode* FindMax(treeNode *node)
{
        if(node==NULL)
        {
                /* There is no element in the tree */
                return NULL;
        }
        if(node->right) /* Go to the left sub tree to find the min element */
                FindMax(node->right);
        else 
                return node;
}

treeNode * Insert(treeNode *node,int data)
{
        if(node==NULL)
        {
                treeNode *temp;
                temp = (treeNode *)malloc(sizeof(treeNode));
                temp -> data = data;
                temp -> left = temp -> right = NULL;
                return temp;
        }

        if(data >(node->data))
        {
                node->right = Insert(node->right,data);
        }
        else if(data < (node->data))
        {
                node->left = Insert(node->left,data);
        }
        /* Else there is nothing to do as the data is already in the tree. */
        return node;

}

treeNode * Delete(treeNode *node, int data)
{
        treeNode *temp;
        if(node==NULL)
        {
                printf("Element Not Found");
        }
        else if(data < node->data)
        {
                node->left = Delete(node->left, data);
        }
        else if(data > node->data)
        {
                node->right = Delete(node->right, data);
        }
        else
        {
                /* Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree */
                if(node->right && node->left)
                {
                        /* Here we will replace with minimum element in the right sub tree */
                        temp = FindMin(node->right);
                        node -> data = temp->data; 
                        /* As we replaced it with some other node, we have to delete that node */
                        node -> right = Delete(node->right,temp->data);
                }
                else
                {
                        /* If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child */
                        temp = node;
                        if(node->left == NULL)
                                node = node->right;
                        else if(node->right == NULL)
                                node = node->left;
                        free(temp); /* temp is longer required */ 
                }
        }
        return node;

}

treeNode * Find(treeNode *node, int data)
{
        if(node==NULL)
        {
                /* Element is not found */
                return NULL;
        }
        if(data > node->data)
        {
                /* Search in the right sub tree. */
                return Find(node->right,data);
        }
        else if(data < node->data)
        {
                /* Search in the left sub tree. */
                return Find(node->left,data);
        }
        else
        {
                /* Element Found */
                return node;
        }
}