Binary Tree

A binary tree is a structure comprising nodes, where each node has the following 3 components:

1. Data element: Stores any kind of data in the node

2. Left pointer: Points to the tree on the left side of node

3. Right pointer: Points to the tree on the right side of the node

Commonly-used terminologies

• Root: Top node in a tree

• Child: Nodes that are next to each other and connected downwards

• Parent: Converse notion of child

• Siblings: Nodes with the same parent

• Descendant: Node reachable by repeated proceeding from parent to child

• Ancestor: Node reachable by repeated proceeding from child to parent.

• Leaf: Node with no children

• Internal node: Node with at least one child

• External node: Node with no children

struct node
{
         int data;                  // Data element
         struct node * left;          // Pointer to left node
         struct node * right;         // Pointer to right node
};

Binary Search Tree

For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be the data of the root. The data of all the nodes in the right subtree of the root node should be the data of the root.

Traversing the tree

There are mainly three types of tree traversals.

• Pre-order traversal - In this traversal technique the traversal order is root-left-right i.e.

  • Process data of root node

  • First, traverse left subtree completely

  • Then, traverse right subtree

    void perorder(struct node*root)
    {
        if(root)
        {
            printf("%d ",root->data);    //Printf root->data
            preorder(root->left);    //Go to left subtree
            preorder(root->right);     //Go to right subtree
        }
    }

• Post-order traversal - In this traversal technique the traversal order is left-right-root.

  • Process data of left subtree

  • First, traverse right subtree

  • Then, traverse root node

    void postorder(struct node*root)
    {
        if(root)
        {
            postorder(root->left);    //Go to left sub tree
            postorder(root->right);     //Go to right sub tree
            printf("%d ",root->data);    //Printf root->data
        }
    }

• In-order traversal - In in-order traversal, do the following:

  • First process left subtree (before processing root node)

  • Then, process current root node

  • Process right subtree

    void inorder(struct node*root)
    {
        if(root)
        {
            inorder(root->left);    //Go to left subtree
            printf("%d ",root->data);    //Printf root->data
            inorder(root->right);     //Go to right subtree
        }
    }