Program to Implement Binary Tree using the Linked List

Q. Program to implement Binary Tree using the linked list

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

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.
When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
Define another class which has an attribute root.
1. Root represents the root node of the tree and initialize it to null.
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.
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.

Solution

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 emptyn”);          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

Next TopicPrograms List

Q. Program to implement Binary Tree using the linked list

Explanation

Algorithm

Solution

Python

C

JAVA

C#

PHP

Wind Energy

Basics of PyTorch

You may also like