Binary Trees

A tree has a finite set of elements called nodes. It has a unique node called the root node, where the remaining nodes are a disjoint collection of subtrees. A binary tree is a tree whose elements have two children at maximum. It is considered as a data structure composed of elements that are characterized by two link fields, left and right children. A leaf node contains 0 children meaning both children point to a NULL value.

A binary search tree is a special type of a binary tree. These terms are sometimes used interchangeably in some articles, so do not be confused. For this purpose, I’ll limit my article to binary trees in general.

First let’s define the structure to be used.

#include <stdio.h>
#include <stdlib.h>
	
typedef char DATA;
	
struct node {
        DATA d;
        struct node *left;
        struct node *right;
};
	
typedef struct node NODE;
typedef struct NODE *BINTREE;

[Creating a Binary Tree]

Dynamic allocation.

BINTREE new_node()
{
        return (malloc(sizeof(NODE)));
}

Of course we have to initialize the node.

BINTREE init_node(DATA d1, BINTREE p1, BINTREE p2)
{
        BINTREE t;
	
        t = new_node();
        t -> d = d1;
        t -> left = p1;
        t -> right = p2;
        return t;
}

We will generate a tree from an array recursively.

BINTREE create_tree(DATA a[], int i, int size)
{
        if (i >= size)
                return NULL;
        else
                return (init_node(a[i],
                        create_tree(a, 2 * i + 1, size),
                        create_tree(a, 2 * i + 2, size)));
}

[Binary Tree Traversals]

There are several ways to traverse in a binary tree. Luckily, I have leared something during our CS 213 Data Structures class. Thanks to Sir Greg. Here are three ways presented:

Inorder Traversal: Left Node Right (LNR)
Preorder Traversal: Node Left Right (NLR)
Postorder Traversal: Left Right Node (LRN)

The standard way of implementing this of course is again by recursion.

Inorder Traversal

void inorder(BINTREE root)
{
        if (root != NULL) {
                inorder(root -> left);
                printf("%c ", root -> d);
                inorder(root -> right);
        }
}

Preorder Traversal

void preorder(BINTREE root)
{
        if (root != NULL) {
                printf("%c ", root -> d);
                preorder(root -> left);
                preorder(root -> right);
        }
}

Postorder Traversal

void postorder(BINTREE root)
{
        if (root != NULL) {
                postorder(root -> left);
                postorder(root -> right);
                printf("%c ", root -> d);
        }
}

Hope this article will be useful to students taking up Data Structures and Algorithms.