Data Structures and Algorithms (DSA) using C# .NET Core — Binary Trees and Binary Tree Types II

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

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.

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.

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).
   

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.

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.