loader image

Binary Tree

A Binary tree is a special tree where each node can have no more than two children. A non-empty binary tree consist of the following:

  • A node called the root node.
  • A left sub-tree.
  • A right sub-tree.

Both the sub-trees are themselves binary trees.

binary tree example
Binary Tree

Types of Binary Trees

Complete Binary Tree

The tree T is said to be complete if,

  • All it’s levels, except possibly the last, must be completely filled.
  • All the leaf nodes must appear as far left as possible.
complete binary tree 1
A Complete Binary Tree

Full Binary Tree

A full binary tree is a special type of tree in which the leaf nodes will have zero children and other non-leaf nodes will have exactly 2 children.

full binary tree 1
A Full Binary Tree

Representation of Binary Tree

Binary trees can be maintained in memory using either an array or a linked list.

Sequential representation of binary trees

The simplest technique for representing a binary tree is to store the elements using a one-dimensional array.

Suppose we are using a one-dimensional array TREE to store the elements of a tree. The rules for a sequential binary tree are as follows:

  • The root of the tree will be stored in TREE[0].
  • If an element is stored in TREE[K], then
    • It’s left child is stored in TREE[2K + 1].
    • It’s right child is stored in TREE[2K + 2].

A tree of height h will require an array of maximum size 2h-1. A tree is empty if TREE[0] = NULL.

The following figure shows a binary tree and its corresponding sequential representation.

Binary tree and its sequential representation
Binary tree and its sequential
Binary tree and its sequential representation

This method is inefficient unless the tree is (almost) full. Also, it is not possible to add a new node if the tree is already full.

Linked representation of binary trees

Every node in a linked representation of binary tree will contain three parts:

  • The data element.
  • A pointer to the left node.
  • A pointer to the right node.

It can be represented by a structure.

struct node {
    struct node *left;
    int data;
    struct node *right;

The root node is pointed by a pointer ROOT. The tree is empty if ROOT = NULL

The schematic diagram of the linked representation of the binary tree is shown below.

Linked representation of a binary tree
Linked representation of a binary tree

Applications of Binary Tree

  • For rapid and easy access to data.
  • Routing algorithms.
  • To implement heap data structure.
  • Syntax tree, Binary Search Tree, Hash Trees, Treap, T-tree, etc.
Notify of
Inline Feedbacks
View all comments