Binary Search Trees

Created by Flash- Nguyen Duc Quan
------------------------------------------------------------------------------------------------------------------

1. Definitions

  A binary tree is made of nodes where each node contains a "left", a "right" reference, and a data element. (Binary tree is an extended part of linked data structure). The node at top A is named root.

Figure 1: Binary tree

Every node (excluding a root) in tree is connected by a directed edge from exactly one other node. This node is called a parent. Beside, each node can connect to arbitrary node number of node (it is two in this situation), called children

Some tree terminology we should know:

• Root node: A
• Leaf node (External node): Node without children :  H, I, J, K, L
• Internal node: Node are not leaves:  B, D, E C, F, G.
• Siblings: Nodes with the same parent: such as: B and C, D and E....
• The depth of a node is the number of node from the root to the node. Ex: Depth of node B is 2
• The height of a node is the number of node from the node to the deepest leaf. Ex: Height of Node B is 3
• The height of a tree is a height of the root. Ex: In figure 1, this tree has height equal to 4.
• A compete binary tree: If height of tree is h, then every node which has depth lower than (h - 1), must have 2 children. Example Figure 2 a)

Figure 2: e) a complete binary tree , f) a full binary tree

• A full binary tree is a binary tree: Every node has which depth lower or equal to (h-1) must have two children

2. Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move sub-trees around with minimum effort

3. Representation of Binary Trees.

3.1 Representation by an array

With full binary tree, we can number easily for each node on the tree from depth 1 to higher depth, from left to right. Therefore, the children of node i is 2i and 2i + 1. Parent of node j is node j div 2. After that we can store tree by array T, i-th node is stored by element T[i].

Figure 3: nodes are numbered

The binary tree in Figure 3 can be stored liked Figure 4.

Figure 4: Representation by array

3.2 Representation by linked list

Figure 5: Node Structure of Binary Tree

Each node has 3 domains:

• Info: Store value of node
• Left Pointer: a pointer points to its left child.
• Right Pointer: a pointer points to its right child.

The Binary tree represented by linked list is shown in Figure 1.

4. Traversals

A traversal is a process that visits all the nodes in the 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 (or Level Order)

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

• PreOrder traversal - visit the parent first and then left and right children;

// Result with Figure 1: A B D H I E J C F K G L

Procedure Visit (N) // Suppose N is root of tree
begin
     if N != null then
          begin
           Print value of node N;
           Visit (left node of N);
           Visit (right node of N);
     end;
end;

• InOrder traversal - visit the left child, then the parent and the right child;

// Result with Figure 1: H D I B E J A K F C G L

Procedure Visit (N) // Suppose N is root of tree
begin
    if N != null then
        begin
        Visit (left node of N);
        Print value of node N;
        Visit (right node of N);
     end;
end;

• PostOrder traversal - visit left child, then the right child and then the parent;

// Result with Figure 1: H I D J E B K F L G C A

Procedure Visit (N) // Suppose N is root of tree
begin
    if N != null then
         begin
         Visit (left node of N);
         Visit (right node of N);
         Print value of node N;
    end;
end;

LevelOder traversal: This traversal visits nodes by levels from top to bottom and from left to right.
Result with Figure 1: A B C D E F G H I J K L

5. Funtions to binary trees

5.1 Declare a struct: node
// code

struct node
{
   int a;// Value of  node
   node *letf , *right;// Two Pointers to left and right nodes
};

5.2 Init a tree
// code

struct node *head = NULL;

5.3 Check a tree, empty or not
// code

int empty_tree(nodeptr root)
{
   if(root == NULL)   return 1;
   else return 0;
}

5.4 Generate a tree
// code

void generate(struct node **head, int num)
{
    struct node *temp = *head, *prev = *head;
    
    // Neu la lan dau thi do la root
    if (*head == NULL)
    {
        *head = (struct node *)malloc(sizeof(struct node));
        (*head)->a = num;
        (*head)->left = (*head)->right = NULL;
    }
    else
    {
        while (temp != NULL)
        {
            if (num > temp->a)  
            {
                prev = temp;
                temp = temp->right;
            }
            else                
            {
                prev = temp;
                temp = temp->left;
            }
        }
        temp = (struct node *)malloc(sizeof(struct node)); 
        temp->a = num;

        // Noi node cha den node moi tao
        if (num >= prev->a)    
        {
            prev->right = temp;    
        }
        else
        {
            prev->left = temp;
        }
    }
}

5.5 Delete tree
// code

void delete(struct node **head)
{
    if (*head != NULL)
    {
        if ((*head)->left)
        {
            delete(&(*head)->left);
        }
        if ((*head)->right)
        {
            delete(&(*head)->right);
        }
        free(*head);
    }
}

5.6 Tree Depth and Tree Height
// code

int TreeDepth(struct node *root)
{
    if(root == NULL)
    {
        return 0;
    }
    int nLeft = TreeDepth(root->left);
    int nRight = TreeDepth(root->right);
    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}

5.7 Find largest number on tree
// code

void largest(struct node *root)
{
    if (root->right  == NULL) 
    {
        printf("-------------->Largest element is %d <---------------- n="" root-="">a);
    }
    while (root != NULL && root->right != NULL)
    {
        root = root->right;
    }
    printf("\n---------------> Largest value is %d <----------------- n="" root-="">a);
}

5.8 Counting the number of nodes in a tree
// code

int count_num_nodes(struct node *root)
{
    int c = 1;
 
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        if(root -> left != NULL)
        {
            c += count_num_nodes(root->left);
        }
        if(root -> right != NULL)
        {
            c += count_num_nodes(root->right);
        }
        return c;
    }
}

5.9 Count number of leaf nodes

void count_leaf(struct node * root)
{
    if (root == NULL)
    {
        return;
    }
    if (root->left == NULL && root->right == NULL)
    {
        count++;
    }
    count_leaf(root->left);
    count_leaf(root->right);
}

// code

5.10 Traversal
a. Depth First Search: Pre-order
// code

void DFS_Pre_Order(struct node *head)
{
    if (head != NULL)
    {
        printf("%d  ", head->a);
        if (head->left != NULL)
        {
            DFS_Pre_Order(head->left);
        }
        if (head->right != NULL)
        {
            DFS_Pre_Order(head->right);
        }
    }
}

b. Depth First Search: In_order
//code

void DFS_In_Order(struct node *head)
{
    if (head != NULL)
    {
        if (head->left != NULL)
        {
            DFS_In_Order(head->left);
        }

        printf("%d  ", head->a);

        if (head->right != NULL)
        {
            DFS_In_Order(head->right);
        }    
    }
}

c. Depth First Search: Post-order
//code

void DFS_Post_Order(struct node *head)
{
    if (head != NULL)
    {
        if (head->left != NULL)
        {
            DFS_Post_Order(head->left);
        }
        if (head->right != NULL)
        {
            DFS_Post_Order(head->right);
        }
        printf("%d  ", head->a);
    }
}

5.11 Search a node on tree using recursion algorithm
// code

int search_recursion(struct node *head, int key)
{
    if (head != NULL)  
    {
        if(key > head->a)
        {
            return search_recursion(head->right, key);
        }
        else
        {
            if(key < head -> a)
            {
                return search_recursion(head->left, key);
            }
            else
            {
                return 1;
            }
        }
    }
    return 0;
}

5.12 Search a node on tree not using recursion algorithm

// code

struct node *search_nonrecurion(struct node *head, int key, struct node **parent)
{
    while (head != NULL)
    {
        if (key > head->a)
        {
            *parent = head;
            head = head->right;
        }
        else 
        {
            if (key < head->a)
            {
                *parent = head;
                head = head->left;    
            }
            else
            {
                return head;
            }   
        }
    }
    return NULL;
}

5.13 Find n-th Node in Pre-order Traversal
// code

void nthpreorder(struct node *root, int n, struct node **nthnode, int *var)
{

    if (root)
    {
        if ( ++(*var) == n)
        {
            printf("\n----------Found %dth node------------\n", n);
            *nthnode = root;
        }
        else
        {
            if(root->left != NULL)
            {
                nthpreorder(root->left, n , nthnode,var);            
            }
            if(root ->right != NULL)
            {
                nthpreorder(root->right, n , nthnode,var);
            }
        }
    }
    else
    {
        printf("There is no tree in this program.\n");
    }
}

5.14 Find n-th Node in In-order Traversal
// code

void nthinorder(struct node *root, int n, struct node **nthnode,int *var)
{
    if (root)
    {
        if(root->left != NULL)
        {
            nthinorder(root->left, n , nthnode,var);            
        }
        if (++(*var) == n)
        {
            printf("\n Found %dth node\n", n);
            *nthnode = root;
        }
        if(root ->right != NULL)
        {
            nthinorder(root->right, n , nthnode,var);
        }
    }
    else
    {
        printf("There is no tree in this program.\n");
    }
}

5.15 Find n-th Node in Post-order Traversal
// code

void nthpostorder(struct node *root, int n, struct node **nthnode,int *var)
{
    if (root)
    {
        if(root->left != NULL)
        {
            nthpostorder(root->left, n , nthnode, var);            
        }
        if(root ->right != NULL)
        {
            nthpostorder(root->right, n , nthnode, var);
        }
        if (++(*var) == n)
        {
            printf("\n Found %dth node\n", n);
            *nthnode = root;
        }
    }
    else
    {
        printf("There is no tree in this program.\n");
    }
}

5.16 The main function
// code

int main()
{
    struct node *head = NULL;
    int choice = 0, num, flag = 0, key;
    int var = 0;
    struct node *result = (struct node *)malloc(sizeof(result));
    struct node *parent = (struct node *)malloc(sizeof(parent));
    do
    {
        printf("\nEnter your choice:\n1. Insert\n2. Perform DFS - Pre-order Traversal\n3. Perform DFS - In-order Traversal\n\
4. Perform DFS - Pos-order Traversal\n5. Search using recursion\n6. Search using non-recursion\n\
7. Find nth node follow preorder traversal\n8. Find nth node follow inorder traversal\n\
9. Find nth node follow postorder traversal\n10. Find largest node on tree\n11. Count number of leaf nodes\n\
12. Find number of nodes on tree\n13. Find Depth of tree\n14. Delete a node on tree\n15. Exit\nChoice: ");
        scanf("%d", &choice);
        switch(choice)
        {
        case 1: 
            printf("Enter element to insert: ");
            scanf("%d", &num);
            generate(&head, num);
            break;
        case 2: 
            DFS_Pre_Order(head);
            break;
        case 3:
            DFS_In_Order(head);
            break;
        case 4: 
            DFS_Post_Order(head);
            break;

        // Search node in tree (where value of any node is matched or not with entered number) using recursion
        case 5:    
            printf("Enter element to search: ");
            scanf("%d", &key);
            flag = search_recursion(head, key);
            if (flag)
            {
                printf("---------------> Key = [%d] found in tree <----------------\n",key);
            }
            else
            {
                printf("---------------> Key = [%d] not found <-------------------\n",key);
            }
            break;

        // Search node in tree (where value of any node is matched or not with entered number) using non-recursion
        case 6:
            printf("Enter element to search: ");
            scanf("%d", &key);
            result = search_nonrecurion(head, key,&parent);
            if (result != NULL)
            {
                printf("---------------> Key found in tree <----------------\n");
            }
            else
            {
                printf("---------------> Key not found <-------------------\n");
            }
            break;

        // Find n-th node by using preorder traversal
        case 7:
            printf("Enter nth node which you want to find: ");
            scanf("%d", &key);
            result = NULL;
            var = 0;
            nthpreorder(head,key,&result,&var);
            if(result != NULL)
            {
                printf("\nResult ---->[%d]\n", result->a);
            }
            else{
                printf("\n---------> There is no node which satisfies.<-----------------\n");
            }
            break;

        // Find n-th node by using inorder traversal
        case 8:
            printf("Enter nth node which you want to find: ");
            scanf("%d", &key);
            result = NULL;
            var = 0;
            nthinorder(head,key,&result,&var);
            if(result != NULL)
            {
                printf("\nResult ---->[%d]\n", result->a);
            }
            else{
                printf("\n---------> There is no node which satisfies.<-----------------\n");
            }
            break;

        // Find n-th node by using postorder traversal
        case 9:
            printf("Enter nth node which you want to find: ");
            scanf("%d", &key);
            result = NULL;
            var = 0;
            nthpostorder(head,key,&result,&var);
            if(result != NULL)
            {
                printf("\nResult ---->[%d]\n", result->a);
            }
            else{
                printf("\n---------> There is no node which satisfies.<-----------------\n");
            }
            break;
        // Find largest node on tree
        case 10:
            largest(head);
            break;
        // Find number of leaf nodes
        case 11:
            count = 0;
            count_leaf(head);
            printf("--------> Number of leaf nodes = %d <-----------\n", count);
            break;
        //Find number of nodes on tree
        case 12:
            count = count_num_nodes(head);
            printf("-------------> Number of nodes on tree = %d <-----------\n", count);
            count  = 0;
            break;
        // Find depth of tree
        case 13:
            count = TreeDepth(head);
            printf("\n-----------> Depth of tree = %d <-------------\n",count);
            count = 0;
            break;
        // Delete a node on tree.
        case 14:
            printf("Enter value of node which you want to delete = ");
            scanf("%d", &key);
            result = search_nonrecurion(head,key,&parent);
            DeleteNode(&result,&parent);
            break;
        case 15:
            delete(&head);
            printf("Memory Cleared\nPROGRAM TERMINATED\n");
            break;
        default: 
            printf("Not a valid input, try again\n");
        }
    } while (choice != 15);
    return 0;
}

Download full code here:

References
1: http://cslibrary.stanford.edu/110/BinaryTrees.html
2: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
3: http://quiz.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/
4: http://www.sanfoundry.com/c-programming-examples-on-trees/