# Program to Implement Binary Tree using the Linked List

Program to Implement Binary Tree using the Linked List on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

## 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

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.

### 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

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) {
}
else {
//If node has no left child, make newNode as left child
if(node.left == null) {
node.left = newNode;
}
//If node has left child but no right child, make newNode as right child
else {
node.right = newNode;
}
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