Q:

Program to implement Binary Tree using the linked list

belongs to collection: Tree Programs

robaa
Save to bookmark
|
2022-11-09
|
  274 
0

Explanation

In this program, we need to create the binary tree by inserting nodes and displaying nodes in inorder fashion. A typical binary tree can be represented as follows:

In the binary tree, each node can have at most two children. Each node can have zero, one or two children. Each node in the binary tree contains the following information:

Data that represents value stored in the node.

Left that represents the pointer to the left child.

Right that represents the pointer to the right child.

Algorithm

  1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has an attribute root.
    1. Root represents the root node of the tree and initialize it to null.
  4. insert() will add a new node to the tree:
    1. It checks whether the root is null, which means the tree is empty. It will add the new node as root.
    2. Else, it will add root to the queue.
    3. The variable node represents the current node.
    4. First, it checks whether a node has a left and right child. If yes, it will add both nodes to queue.
    5. If the left child is not present, it will add the new node as the left child.
    6. If the left is present, then it will add the new node as the right child.
  5. Inorder() will display nodes of the tree in inorder fashion.
    1. It traverses the entire tree then prints out left child followed by root then followed by the right child.

Output:

Binary tree after insertion: 1
Binary tree after insertion: 2 1 3
Binary tree after insertion: 4 2 5 1 3
Binary tree after insertion: 4 2 5 1 6 3 7
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-09
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#Represent a node of binary tree  
class Node:  
    def __init__(self,data):  
        #Assign data to the new node, set left and right children to None  
        self.data = data;  
        self.left = None;  
        self.right = None;  
   
class BinaryTree:  
    def __init__(self):  
        #Represent the root of binary tree  
        self.root = None;  
          
    #insertNode() will add new node to the binary tree  
    def insertNode(self, data):  
        #Create a new node  
        newNode = Node(data);  
          
        #Check whether tree is empty  
        if(self.root == None):  
            self.root = newNode;  
            return;  
        else:  
            queue = [];  
            #Add root to the queue  
            queue.append(self.root);  
              
            while(True):  
                node = queue.pop(0);  
                #If node has both left and right child, add both the child to queue  
                if(node.left != None and node.right != None):  
                    queue.append(node.left);  
                    queue.append(node.right);  
                else:  
                    #If node has no left child, make newNode as left child  
                    if(node.left == None):  
                        node.left = newNode;  
                        queue.append(node.left);  
                    else:  
                        #If node has left child but no right child, make newNode as right child  
                        node.right = newNode;  
                        queue.append(node.right);  
                    break;  
                      
    #inorder() will perform inorder traversal on binary search tree  
    def inorderTraversal(self, node):  
          
        #Check whether tree is empty  
        if(self.root == None):  
            print("Tree is empty");  
            return;  
        else:  
            if(node.left != None):  
                self.inorderTraversal(node.left);  
            print(node.data),  
            if(node.right!= None):  
                self.inorderTraversal(node.right);  
                  
bt = BinaryTree();  
#Add nodes to the binary tree  
   
bt.insertNode(1);  
#1 will become root node of the tree  
print("Binary tree after insertion");  
#Binary after inserting nodes  
bt.inorderTraversal(bt.root);  
   
bt.insertNode(2);  
bt.insertNode(3);  
#2 will become left child and 3 will become right child of root node 1  
print("\nBinary tree after insertion");  
#Binary after inserting nodes  
bt.inorderTraversal(bt.root);  
   
bt.insertNode(4);  
bt.insertNode(5);  
#4 will become left child and 5 will become right child of node 2  
print("\nBinary tree after insertion");  
#Binary after inserting nodes  
bt.inorderTraversal(bt.root);  
   
bt.insertNode(6);  
bt.insertNode(7);  
#6 will become the left child and 7 will become the right child of node 3  
print("\nBinary tree after insertion");  
#Binary after inserting nodes  
bt.inorderTraversal(bt.root);

 

Output:

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

 

C

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
   
//Represent a node of binary tree  
struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};  
   
//Represent the root of binary tree  
struct node *root = NULL;  
   
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode, set left and right child to NULL  
    newNode->data = data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
      
    return newNode;  
}  
   
//Represent a queue  
struct queue  
{  
    int front, rear, size;  
    struct node* *arr;  
};  
   
//createQueue() will create a queue  
struct queue* createQueue()  
{  
    struct queue* newQueue = (struct queue*) malloc(sizeof( struct queue ));  
   
    newQueue->front = -1;  
    newQueue->rear = 0;  
    newQueue->size = 0;  
  
    newQueue->arr = (struct node**) malloc(100 * sizeof( struct node* ));  
   
    return newQueue;  
}  
   
//Adds a node to queue  
void enqueue(struct queue* queue, struct node *temp){  
    queue->arr[queue->rear++] = temp;  
    queue->size++;  
}  
   
//Deletes a node from queue  
struct node *dequeue(struct queue* queue){  
    queue->size--;  
    return queue->arr[++queue->front];  
}  
   
   
//insertNode() will add new node to the binary tree  
void insertNode(int data) {  
    //Create a new node  
    struct node *newNode = createNode(data);  
    //Check whether tree is empty  
    if(root == NULL){  
        root = newNode;  
        return;  
    }  
    else {  
        //Queue will be used to keep track of nodes of tree level-wise  
        struct queue* queue = createQueue();  
        //Add root to the queue  
        enqueue(queue, root);  
          
        while(true) {  
            struct node *node = dequeue(queue);  
            //If node has both left and right child, add both the child to queue  
            if(node->left != NULL && node->right != NULL) {  
                enqueue(queue, node->left);  
                enqueue(queue, node->right);  
            }  
            else {  
                //If node has no left child, make newNode as left child  
                if(node->left == NULL) {  
                    node->left = newNode;  
                    enqueue(queue, node->left);  
                }  
                //If node has left child but no right child, make newNode as right child  
                else {  
                    node->right = newNode;  
                    enqueue(queue, node->right);  
                }  
                break;  
            }  
        }  
    }  
}  
   
//inorder() will perform inorder traversal on binary search tree  
void inorderTraversal(struct node *node) {  
    //Check whether tree is empty  
    if(root == NULL){  
        printf("Tree is empty\n");  
        return;  
    }  
    else {  
            
        if(node->left != NULL)  
            inorderTraversal(node->left);  
        printf("%d ", node->data);  
        if(node->right != NULL)  
            inorderTraversal(node->right);  
                
        }  
    }  
            
int main(){  
      
    //Add nodes to the binary tree  
    insertNode(1);  
    //1 will become root node of the tree  
    printf("Binary tree after insertion: \n");  
    //Binary after inserting nodes  
    inorderTraversal(root);  
      
    insertNode(2);  
    insertNode(3);  
    //2 will become left child and 3 will become right child of root node 1  
    printf("\nBinary tree after insertion: \n");  
    //Binary after inserting nodes  
    inorderTraversal(root);  
      
    insertNode(4);  
    insertNode(5);  
    //4 will become left child and 5 will become right child of node 2  
    printf("\nBinary tree after insertion: \n");  
    //Binary after inserting nodes  
    inorderTraversal(root);  
      
    insertNode(6);  
    insertNode(7);  
    //6 will become left child and 7 will become right child of node 3  
    printf("\nBinary tree after insertion: \n");  
    //Binary after inserting nodes  
    inorderTraversal(root);  
      
    return 0;  
}

 

 

Output:

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

 

JAVA

import java.util.LinkedList;  
import java.util.Queue;  
   
public class BinaryTree {  
        
      //Represent a node of binary tree  
      public static class Node{  
        int data;  
        Node left;  
        Node right;  
          
        public Node(int data){  
          //Assign data to the new node, set left and right children to null  
          this.data = data;  
          this.left = null;  
          this.right = null;  
        }  
      }  
        
      //Represent the root of binary tree  
      public Node root;  
        
      public BinaryTree(){  
        root = null;  
      }  
        
      //insertNode() will add new node to the binary tree  
      public void insertNode(int data) {  
          //Create a new node  
          Node newNode = new Node(data);  
            
          //Check whether tree is empty  
          if(root == null){  
              root = newNode;  
              return;  
          }  
          else {  
             Queue<Node> queue = new LinkedList<Node>();  
             //Add root to the queue  
             queue.add(root);  
               
             while(true) {  
                 
                 Node node = queue.remove();  
                //If node has both left and right child, add both the child to queue  
                 if(node.left != null && node.right != null) {  
                     queue.add(node.left);  
                     queue.add(node.right);  
                 }  
                 else {  
                    //If node has no left child, make newNode as left child  
                     if(node.left == null) {  
                         node.left = newNode;  
                         queue.add(node.left);  
                     }  
                    //If node has left child but no right child, make newNode as right child  
                     else {  
                         node.right = newNode;  
                         queue.add(node.right);  
                     }  
                     break;  
                 }  
             }  
          }  
      }  
        
      //inorder() will perform inorder traversal on binary search tree  
      public void inorderTraversal(Node node) {  
            
          //Check whether tree is empty  
          if(root == null){  
              System.out.println("Tree is empty");  
              return;  
          }  
          else {  
                
              if(node.left!= null)  
                  inorderTraversal(node.left);  
              System.out.print(node.data + " ");  
              if(node.right!= null)  
                  inorderTraversal(node.right);  
                    
              }        
          }  
        
      public static void main(String[] args) {  
         
        BinaryTree bt = new BinaryTree();  
        //Add nodes to the binary tree  
          
        bt.insertNode(1);  
        //1 will become root node of the tree  
        System.out.println("Binary tree after insertion");  
        //Binary after inserting nodes  
        bt.inorderTraversal(bt.root);  
          
        bt.insertNode(2);  
        bt.insertNode(3);  
        //2 will become left child and 3 will become right child of root node 1  
        System.out.println("\nBinary tree after insertion");  
        //Binary after inserting nodes  
        bt.inorderTraversal(bt.root);  
          
        bt.insertNode(4);  
        bt.insertNode(5);  
        //4 will become left child and 5 will become right child of node 2  
        System.out.println("\nBinary tree after insertion");  
        //Binary after inserting nodes  
        bt.inorderTraversal(bt.root);  
          
        bt.insertNode(6);  
        bt.insertNode(7);  
        //6 will become left child and 7 will become right child of node 3  
        System.out.println("\nBinary tree after insertion");  
        //Binary after inserting nodes  
        bt.inorderTraversal(bt.root);  
          
      }  
    }

 

Output:

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

 

C#

using System;  
using System.Collections.Generic;  
namespace Tree   
{                       
    public class Program  
    {  
        //Represent a node of binary tree  
        public class Node<T>{  
            public T data;  
            public Node<T> left;  
            public Node<T> right;  
              
            public Node(T data) {  
                //Assign data to the new node, set left and right children to null  
                this.data = data;  
                this.left = null;  
                this.right = null;  
            }  
        }  
          
        public class BinaryTree<T>{  
            //Represent the root of binary tree  
            public Node<T> root;  
              
            public BinaryTree(){  
                root = null;  
            }  
              
            //insertNode() will add new node to the binary tree  
            public void insertNode(T data) {  
                //Create a new node  
                Node<T> newNode = new Node<T>(data);  
   
                //Check whether tree is empty  
                if(root == null){  
                  root = newNode;  
                  return;  
                }  
                else {  
                    Queue<Node<T>> queue = new Queue<Node<T>>();  
                    //Add root to the queue  
                    queue.Enqueue(root);  
   
                    while(true) {  
   
                        Node<T> node = queue.Dequeue();  
                        //If node has both left and right child, add both the child to queue  
                        if(node.left != null && node.right != null) {  
                            queue.Enqueue(node.left);  
                            queue.Enqueue(node.right);  
                        }  
                        else {  
                            //If node has no left child, make newNode as left child  
                            if(node.left == null) {  
                                node.left = newNode;  
                                queue.Enqueue(node.left);  
                            }  
                            //If node has left child but no right child, make newNode as right child  
                            else {  
                                node.right = newNode;  
                                queue.Enqueue(node.right);  
                            }  
                            break;  
                        }  
                    }  
                }  
            }  
        
            //inorder() will perform inorder traversal on binary search tree  
            public void inorderTraversal(Node<T> node) {  
                
                //Check whether tree is empty  
                if(root == null){  
                    Console.WriteLine("Tree is empty");  
                    return;  
                }  
                else {  
                    
                    if(node.left!= null)  
                      inorderTraversal(node.left);  
                    Console.Write(node.data + " ");  
                    if(node.right!= null)  
                      inorderTraversal(node.right);  
                }        
            }  
        }  
          
        public static void Main()  
        {  
            BinaryTree<int> bt = new BinaryTree<int>();  
            //Add nodes to the binary tree  
          
            bt.insertNode(1);  
            //1 will become root node of the tree  
            Console.WriteLine("Binary tree after insertion");  
            //Binary after inserting nodes  
            bt.inorderTraversal(bt.root);  
   
            bt.insertNode(2);  
            bt.insertNode(3);  
            //2 will become left child and 3 will become right child of root node 1  
            Console.WriteLine("\nBinary tree after insertion");  
            //Binary after inserting nodes  
            bt.inorderTraversal(bt.root);  
   
            bt.insertNode(4);  
            bt.insertNode(5);  
            //4 will become left child and 5 will become right child of node 2  
            Console.WriteLine("\nBinary tree after insertion");  
            //Binary after inserting nodes  
            bt.inorderTraversal(bt.root);  
   
            bt.insertNode(6);  
            bt.insertNode(7);  
            //6 will become left child and 7 will become right child of node 3  
            Console.WriteLine("\nBinary tree after insertion");  
            //Binary after inserting nodes  
            bt.inorderTraversal(bt.root);                  
        }      
    }  
}

 

Output:

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

 

PHP

<!DOCTYPE html>  
<html>  
<body>  
<?php  
//Represent a node of binary tree  
class Node{  
    public $data;  
    public $left;  
    public $right;  
      
    function __construct($data){  
        //Assign data to the new node, set left and right children to NULL  
        $this->data = $data;  
        $this->left = NULL;  
        $this->right = NULL;  
    }  
}  
class BinaryTree{  
    //Represent the root of binary tree  
    public $root;  
    function __construct(){  
        $this->root = NULL;  
    }  
      
    //insertNode() will add new node to the binary tree  
    function insertNode($data) {  
        //Create a new node  
        $newNode = new Node($data);  
        //Check whether tree is empty  
        if($this->root == NULL){  
            $this->root = $newNode;  
            return;  
        }  
        else {  
            $queue = array();  
            //Add root to the queue  
            array_push($queue, $this->root);  
            while(true) {  
                $node = array_shift($queue);  
                //If node has both left and right child, add both the child to queue  
                if($node->left != NULL && $node->right != NULL) {  
                    array_push($queue, $node->left);  
                    array_push($queue, $node->right);  
                }  
                else {  
                    //If node has no left child, make newNode as left child  
                    if($node->left == NULL) {  
                        $node->left = $newNode;  
                        array_push($queue, $node->left);  
                    }  
                    //If node has left child but no right child, make newNode as right child  
                    else {  
                        $node->right = $newNode;  
                        array_push($queue, $node->right);  
                    }  
                    break;  
                }  
            }  
        }  
    }  
        
    //inorder() will perform inorder traversal on binary search tree  
    function inorderTraversal($node) {  
          
        //Check whether tree is empty  
        if($this->root == NULL){  
            print("Tree is empty <br>");  
            return;  
        }  
        else {  
              
            if($node->left != NULL)  
                $this->inorderTraversal($node->left);  
            print($node->data . " ");  
            if($node->right != NULL)  
                $this->inorderTraversal($node->right);  
        }        
    }    
}  
      
$bt = new BinaryTree();  
//Add nodes to the binary tree  
   
$bt->insertNode(1);  
//1 will become root node of the tree  
print("\nBinary tree after insertion <br>");  
//Binary after inserting nodes  
$bt->inorderTraversal($bt->root);      
   
$bt->insertNode(2);  
$bt->insertNode(3);  
//2 will become left child and 3 will become right child of root node 1  
print("<br> Binary tree after insertion <br>");  
//Binary after inserting nodes  
$bt->inorderTraversal($bt->root);      
   
$bt->insertNode(4);  
$bt->insertNode(5);  
//4 will become left child and 5 will become right child of node 2  
print("<br> Binary tree after insertion <br>");  
//Binary after inserting nodes  
$bt->inorderTraversal($bt->root);      
   
$bt->insertNode(6);  
$bt->insertNode(7);  
//6 will become left child and 7 will become right child of node 3  
print("<br> Binary tree after insertion <br>");  
//Binary after inserting nodes  
$bt->inorderTraversal($bt->root);        
?>  
</body>  
</html>

 

Output:

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Tree Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Program to search a node in a Binary Tree... >>
<< Program to find the total number of possible Binar...