In this story, we will continue on Binary Trees and the type of Binary Trees. Further, we will talk about the Binary Search Tree ( implementation of Binary Tree).

As mentioned in Article 1, A binary tree is a tree where each node can have no more than two children (i.e. 0, 1, or at max 2 children). Fig. 1

Binary Tree

Fig.1. Binary Tree Structure.

Each Binary tree has the following properties.

  1. Every node in a binary tree has at most two children i.e. every node has 0, 1, or 2 children. It cannot have more than two children.
  2. Every child node is labeled as left child and/or right child.
  3. The left child precedes the right child in order of children.

Let's talk about the Type of Binary Trees.

Types of Binary Trees

  1. Full Binary Tree ( proper Binary Tree)
  2. Perfect Binary Tree
  3. Complete Binary Tree
  4. Balanced Binary Tree
  5. Skewed Binary Tree
  6. Degenerate Binary Tree

Full Binary Tree

A full Binary tree is a special type of binary tree where each parent / internal node has 2 or no (0) children. This tree is also known as a Proper binary tree.

Full Binary

Perfect Binary Tree

A perfect binary is a special type of binary tree in which all internal nodes have exactly two nodes, and all leaf nodes are at the same level.

Perfect Binary

Complete Binary Tree

A Complete Binary Tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.

Note. A complete binary tree is like a full binary tree, except it has two major difference

  1. All leaf elements must lean towards the left.
  2. A complete binary tree does not have to be a full binary tree, i.e. does not have to have a right leaf node (right sibling).
    Complete Binary

Balanced Binary Tree

A balanced tree is a binary tree in which the height of the left and the right subtree of any node does not differ by more than 1.

Note. The height of a tree is the height of the root node or the depth of the deepest node.

Balanced Binary

There are a few other types of binary Trees, like the Skewed Binary Tree and Degenerate Binary Tree

Programmatic implementation of Binary Tree (C#)

A Node in a binary tree is represented as a class with data part and two left and right pointer (nodes) to represent another node of the same type.

internal class Node
{
    internal int data;
    internal Node left;
    internal Node right;
    internal Node(int key)
    {
        data = key;
        left = null;
        right = null;
    }
}
internal class TreeTraversal
{
    internal Node root;
    internal TreeTraversal()
    {
        root = null;
    }
}

In the Next section, we will talk about another type of Tree, the Binary Search Tree.