Binary Tree Implementation

Introduction to Binary Tree

A binary Tree is a form of Tree data structure that is connected to almost two other sub-trees containing any form of data. A binary tree is the most efficient data structure, where we can perform various operations on data in a very easier and less complex way. In a binary tree, each node is connected with at most two other children. A binary tree is a rooted tree in which numbering is done from the left side of the node. 

Properties of Binary Trees

1. The maximum height of a Binary Tree having N nodes is N.
2. The Minimum height of a Binary Tree having n nodes is Log₂N.
3. Maximum Nodes in a Binary Tree is (2^h-1), where 'h'  is the height of the Binary Tree.
4. Each Node has two or no child nodes.
5. In No-Empty Binary Tree ( Number of Nodes = Number of edges +1).

Application of Binary Tree

1. Binary Tree Organize hierarchical data in efficient order.
2. A binary Tree is helpful in searching insertion and deletion when data is very large.
3. Binary Tree is used in Network Routing Algorithms.
4. Binary Tree is used in 3D video games for rendering objects.
5. Binary Tree is used in the compression of .jpeg and.mp3 files.
6. Router Algorithm.

Balanced Binary Tree

A balanced Binary Tree is a tree whose difference between the height of left and right subtree for every Node is not more than K(Mostly K=1).

Implementation of Binary Tree

Implementation of Binary Tree can be done in two ways:

• Using Dynamically Created Node
• Using Arrays

Implementation of Binary Tree using Dynamically created node is more efficient than using Arrays.

Implementation of Binary Tree in C++

#include <bits/stdc++.h>

using namespace std;

class Node {

int data;

Node* left;

Node* right;

Node(int val)

{

data = val;

left = NULL;

right = NULL;

}

};

int main()

{

Node* root = new Node(1);

    

root->left = new Node(2);

root->right = new Node(3);

    

root->left->left = new Node(4);

    

return 0;

}

Implementation of Binary Tree in Java

import java.util.*;

public class MyTree {

    static Scanner sc=null;

    public static void main(String[] args) {

        // TODO Auto-generated method stub

    sc=new Scanner(System.in);

            Nodel root =CreateTree();

            inOrder(root);

            System.out.println();

            preOrder(root);

            System.out.println();

            postOrder(root);

    

    }

    static Nodel CreateTree()

    {

        Nodel root=null;

        System.out.println("Enter the Number : ");

        int data=sc.nextInt();

        if(data==-1) { return null;}

        root= new Nodel(data);

        System.out.println("Enter the element left of " + data);

        root.left=CreateTree();

        System.out.println("Enter the element Right of " + data);

        root.right=CreateTree();

        return root;

        

        

        

        

    }

    public static void inOrder(Nodel root)

    {

        

        if(root==null) return;

        inOrder(root.left);

        System.out.print(root.data);

        inOrder(root.right);

        

        

    }

public  static void preOrder(Nodel root)

    {

        

        if(root==null) return;

        System.out.print(root.data);

        preOrder(root.left);

        

        preOrder(root.right);

        

        

    }

    public static void postOrder(Nodel root)

    {

        

        if(root==null) return;

        

        postOrder(root.left);

        postOrder(root.right);

        System.out.print(root.data);

        

    }

}

class Nodel 

{

    Nodel left ,right;

    int data;

    public Nodel(int data)

    {

        this.data=data;

    }

    

}

Types of Transversal in Binary Tree

There are mainly three types of tranversal in Binary Tree

• Inorder Transversal
• Postorder Transversal
• PreOrder Transversal

we will discuss about these transversal in our upcoming Blogs so stay tuned with us.