Binary Tree Data Structure

A binary tree is one of the types of tree data structure. It is one of the widely used abstract data structures that simulates a hierarchical tree structure. A Binary tree has only 2 child nodes at maximum.

In this article, we will learn about binary trees, different types of binary trees and it’s implementations in different programming languages.

Binary tree

A binary tree is a type of tree data structure where a parent node can have a maximum of 2 child nodes. The binary name itself means 2. Each parent node can have 0, 1, or 2 child nodes only. Each node in a binary tree has three parts:

• Data
• Address of left child node
• Address of right child node

Types of binary tree

1. Full Binary Tree

Here, each node in a tree has either 0 or exactly 2 child nodes. A full Binary tree is also known as a proper binary tree.

2. Perfect binary tree

Here, each parent node has exactly 2 child nodes and all child nodes are at the same level.

3. Complete binary tree

A complete binary tree is a version of a full binary tree with 2 major differences;

1. Each level must be filled

2. All leaf elements must lean towards left

3. t is not compulsory for a left child node to have a right sibling node. A complete Binary tree need not necessarily be a full binary tree

4. Degenerate tree

Each node in a degenerate tree has only 0 or 1 child node. The child node can either be the left or right child node. A degenerate tree is also known as a Pathological tree.

5. Skewed Binary Tree

A skewed Binary tree is a version of a Degenerate Binary Tree where it is dominated by either left or right child nodes only. Hence there can be a left Skewed binary tree or a right-skewed binary tree.

6. Balanced Binary Tree

In a Balanced binary tree, the difference between the height of the left and right subtree of each node is either 0 or 1.

Traversing through Binary Tree

Unlike linear data structures, nonlinear data structures like graphs and trees have multiple ways for traversing from the root node to the leaf node. There are three ways of traversing through a tree:

• Inorder traversal
• Preorder traversal
• Postorder traversal

Let us consider a tree:

1. Inorder traversal

Procedure

• Traverse the left subtree
• Visit the root
• Traverse the right subtree

Inorder traversal returns nodes in non-decreasing order in case of a binary search tree.

Inorder Traversal of the above tree is: 5 4 3 1 2 6

2. Preorder traversal

Procedure

• Visit the root
• Traverse the left subtree in preorder
• Traverse the right subtree in preorder

Preorder traversal is helpful while creating a copy of the tree. It returns the prefix expression of an expression tree.

Preorder Traversal or above tree is: 1 4 5 3 2 6

3. Postorder traversal

Procedure

• Traverse the left subtree in preorder
• Traverse the right subtree in preorder
• Visit the root

Postorder traversal is used to delete the tree. It returns the postfix expression of the expression tree.

Postorder Traversal or above tree is: 5 4 3 6 2 1

Traversal of Binary Tree in C

#include <stdio.h>
#include <stdlib.h>

struct node 
{
  int data;
  struct node* leftChild;
  struct node* rightChild;
};

struct node* newNode(int data)
{
  struct node* node
    = (struct node*)malloc(sizeof(struct node));
  node->data = data;
  node->leftChild = NULL;
  node->rightChild = NULL;

  return (node);
}

void PostorderTraversal(struct node* node)
{
  if (node == NULL)
    return;

  PostorderTraversal(node->leftChild);
  PostorderTraversal(node->rightChild);
  printf("%d ", node->data);
}

void InorderTraversal(struct node* node)
{
  if (node == NULL)
    return;

  InorderTraversal(node->leftChild);
  printf("%d ", node->data);
  InorderTraversal(node->rightChild);
}

void PreorderTraversal(struct node* node)
{
  if (node == NULL)
    return;
    
  printf("%d ", node->data);
  PreorderTraversal(node->leftChild);
  PreorderTraversal(node->rightChild);
}

int main()
{
  struct node* root = newNode(1);
  root->leftChild = newNode(4);
  root->rightChild = newNode(2);
  root->leftChild->leftChild = newNode(5);
  root->leftChild->rightChild = newNode(3);
  root->rightChild->rightChild = newNode(6);

  printf("\nPreorder traversal \n");
  PreorderTraversal(root);

  printf("\nInorder traversal  \n");
  InorderTraversal(root);

  printf("\nPostorder traversal  \n");
  PostorderTraversal(root);

  
  return 0;
}

Binary Tree Traversal in C++

#include <iostream>
using namespace std;

struct node 
{
  int data;
  struct node* leftChild;
  struct node* rightChild;
};

struct node* newNode(int data)
{
  struct node* node
    = (struct node*)malloc(sizeof(struct node));
  node->data = data;
  node->leftChild = NULL;
  node->rightChild = NULL;

  return (node);
}

void PostorderTraversal(struct node* node)
{
  if (node == NULL)
    return;

  PostorderTraversal(node->leftChild);
  PostorderTraversal(node->rightChild);
  cout << " " << node->data;
}

void InorderTraversal(struct node* node)
{
  if (node == NULL)
    return;

  InorderTraversal(node->leftChild);
  cout << " " << node->data;
  InorderTraversal(node->rightChild);
}

void PreorderTraversal(struct node* node)
{
  if (node == NULL)
    return;
    
  cout << " " << node->data;
  PreorderTraversal(node->leftChild);
  PreorderTraversal(node->rightChild);
}

int main()
{
  struct node* root = newNode(1);
  root->leftChild = newNode(4);
  root->rightChild = newNode(2);
  root->leftChild->leftChild = newNode(5);
  root->leftChild->rightChild = newNode(3);
  root->rightChild->rightChild = newNode(6);

  cout << "\nPreorder traversal \n";
  PreorderTraversal(root);

  cout << "\nInorder traversal  \n";
  InorderTraversal(root);

  cout <<"\nPostorder traversal  \n";
  PostorderTraversal(root);

  
  return 0;
}

Binary Tree Traversal in JAVA

class Node 
{
  int key;
  Node leftChild, rightChild;

  public Node(int item)
  {
    key = item;
    leftChild = rightChild = null;
  }
}

public class BinaryTree 
{
  Node root;

  BinaryTree() 
  { 
      root = null; 
  }

  void printPostorder(Node node)
  {
    if (node == null)
      return;

    printPostorder(node.leftChild);
    printPostorder(node.rightChild);
    System.out.print(node.key + " ");
  }

  void printInorder(Node node)
  {
    if (node == null)
      return;

    printInorder(node.leftChild);
    System.out.print(node.key + " ");
    printInorder(node.rightChild);
  }
  
  void printPreorder(Node node)
  {
    if (node == null)
      return;
      
    System.out.print(node.key + " ");
    printPreorder(node.leftChild);
    printPreorder(node.rightChild);
  }

  void printPostorder() 
  { 
      printPostorder(root); 
  }
  void printInorder() 
  {
      printInorder(root); 
      
  }
  void printPreorder() 
  {
      printPreorder(root);
  }

  public static void main(String[] args)
  {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(1);
    tree.root.leftChild = new Node(4);
    tree.root.rightChild = new Node(2);
    tree.root.leftChild.leftChild = new Node(5);
    tree.root.leftChild.rightChild = new Node(3);
    tree.root.rightChild.rightChild = new Node(6);

    System.out.println("Preorder traversal of binary tree is ");
    tree.printPreorder();

    System.out.println("\nInorder traversal of binary tree is ");
    tree.printInorder();

    System.out.println("\nPostorder traversal of binary tree is ");
    tree.printPostorder();
  }
}

Traversal of Binary Tree in Python

class Node:
    def __init__(self, key):
        self.leftChild = None
        self.rightChild = None
        self.val = key

    def PreorderTraversal(self):
        print(self.val, end=' ')
        if self.leftChild:
            self.leftChild.PreorderTraversal()
        if self.rightChild:
            self.rightChild.PreorderTraversal()

    def InorderTraversal(self):
        if self.leftChild:
            self.leftChild.InorderTraversal()
        print(self.val, end=' ')
        if self.rightChild:
            self.rightChild.InorderTraversal()

    def PostorderTraversal(self):
        if self.leftChild:
            self.leftChild.PostorderTraversal()
        if self.rightChild:
            self.rightChild.PostorderTraversal()
        print(self.val, end=' ')


root = Node(1)

root.leftChild = Node(4)
root.rightChild = Node(2)

root.leftChild.leftChild = Node(5)
root.leftChild.rightChild = Node(3)

root.rightChild.rightChild = Node(6)

print("Preorder Traversal: ", end="")
root.PreorderTraversal()
print("\nInorder Traversal: ", end="")
root.InorderTraversal()
print("\nPostorder Traversal: ", end="")
root.PostorderTraversal()

Applications of Binary tree

1. Implementing heap data structures
2. creating syntax tree by a compiler for syntax checking
3. A binary tree provides easy access to data
4. A binary tree is used in routers and routing algorithms.

Summary

This was all about Binary Tree in Data Structure. Hope it was great learning for you!!