Implementation of Binary Tree
Below is the code for insertion, deletion and traversal of the binary tree:
#include <stdio.h>
// Node structure to define the structure of the node
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
// Function to create a new node
Node* newNode(int val) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert nodes
Node* insert(Node* root, int data) {
// If tree is empty, new node becomes the root
if (root == NULL) {
root = newNode(data);
return root;
}
// Queue to traverse the tree and find the position to insert the node
Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
Node* temp = queue[front++];
// Insert node as the left child of the parent node
if (temp->left == NULL) {
temp->left = newNode(data);
break;
}
// If the left child is not null, push it to the queue
else
queue[rear++] = temp->left;
// Insert node as the right child of parent node
if (temp->right == NULL) {
temp->right = newNode(data);
break;
}
// If the right child is not null, push it to the queue
else
queue[rear++] = temp->right;
}
return root;
}
/* Function to delete the given deepest node (d_node) in binary tree */
void deletDeepest(Node* root, Node* d_node) {
Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
// Do level order traversal until last node
Node* temp;
while (front != rear) {
temp = queue[front++];
if (temp == d_node) {
temp = NULL;
free(d_node);
return;
}
if (temp->right) {
if (temp->right == d_node) {
temp->right = NULL;
free(d_node);
return;
} else
queue[rear++] = temp->right;
}
if (temp->left) {
if (temp->left == d_node) {
temp->left = NULL;
free(d_node);
return;
} else
queue[rear++] = temp->left;
}
}
}
/* Function to delete element in binary tree */
Node* deletion(Node* root, int key) {
if (!root)
return NULL;
if (root->left == NULL && root->right == NULL) {
if (root->data == key)
return NULL;
else
return root;
}
Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
Node* temp;
Node* key_node = NULL;
// Do level order traversal to find deepest node (temp) and node to be deleted (key_node)
while (front != rear) {
temp = queue[front++];
if (temp->data == key)
key_node = temp;
if (temp->left)
queue[rear++] = temp->left;
if (temp->right)
queue[rear++] = temp->right;
}
if (key_node != NULL) {
int x = temp->data;
key_node->data = x;
deletDeepest(root, temp);
}
return root;
}
// Inorder tree traversal (Left - Root - Right)
void inorderTraversal(Node* root) {
if (!root)
return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
// Preorder tree traversal (Root - Left - Right)
void preorderTraversal(Node* root) {
if (!root)
return;
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Postorder tree traversal (Left - Right - Root)
void postorderTraversal(Node* root) {
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
// Function for Level order tree traversal
void levelorderTraversal(Node* root) {
if (root == NULL)
return;
// Queue for level order traversal
Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
Node* temp = queue[front++];
printf("%d ", temp->data);
// Push left child in the queue
if (temp->left)
queue[rear++] = temp->left;
// Push right child in the queue
if (temp->right)
queue[rear++] = temp->right;
}
}
/* Driver function to check the above algorithm. */
int main() {
Node* root = NULL;
// Insertion of nodes
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\nInorder traversal: ");
inorderTraversal(root);
printf("\nPostorder traversal: ");
postorderTraversal(root);
printf("\nLevel order traversal: ");
levelorderTraversal(root);
// Delete the node with data = 20
root = deletion(root, 20);
printf("\nInorder traversal after deletion: ");
inorderTraversal(root);
return 0;
}
import java.util.LinkedList;
import java.util.Queue;
// Node class to define the structure of the node
class Node {
int data;
Node left, right;
// Parameterized Constructor
Node(int val) {
data = val;
left = right = null;
}
}
public class BinaryTree {
// Function to insert nodes
public static Node insert(Node root, int data) {
// If tree is empty, new node becomes the root
if (root == null) {
root = new Node(data);
return root;
}
// Queue to traverse the tree and find the position to
// insert the node
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
Node temp = q.poll();
// Insert node as the left child of the parent node
if (temp.left == null) {
temp.left = new Node(data);
break;
}
// If the left child is not null push it to the
// queue
else
q.offer(temp.left);
// Insert node as the right child of parent node
if (temp.right == null) {
temp.right = new Node(data);
break;
}
// If the right child is not null push it to the
// queue
else
q.offer(temp.right);
}
return root;
}
/* function to delete the given deepest node
(d_node) in binary tree */
public static void deletDeepest(Node root, Node d_node) {
Queue<Node> q = new LinkedList<>();
q.offer(root);
// Do level order traversal until last node
Node temp;
while (!q.isEmpty()) {
temp = q.poll();
if (temp == d_node) {
temp = null;
d_node = null;
return;
}
if (temp.right != null) {
if (temp.right == d_node) {
temp.right = null;
d_node = null;
return;
} else
q.offer(temp.right);
}
if (temp.left != null) {
if (temp.left == d_node) {
temp.left = null;
d_node = null;
return;
} else
q.offer(temp.left);
}
}
}
/* function to delete element in binary tree */
public static Node deletion(Node root, int key) {
if (root == null)
return null;
if (root.left == null && root.right == null) {
if (root.data == key)
return null;
else
return root;
}
Queue<Node> q = new LinkedList<>();
q.offer(root);
Node temp = new Node(0);
Node key_node = null;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.isEmpty()) {
temp = q.poll();
if (temp.data == key)
key_node = temp;
if (temp.left != null)
q.offer(temp.left);
if (temp.right != null)
q.offer(temp.right);
}
if (key_node != null) {
int x = temp.data;
key_node.data = x;
deletDeepest(root, temp);
}
return root;
}
// Inorder tree traversal (Left - Root - Right)
public static void inorderTraversal(Node root) {
if (root == null)
return;
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}
// Preorder tree traversal (Root - Left - Right)
public static void preorderTraversal(Node root) {
if (root == null)
return;
System.out.print(root.data + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
// Postorder tree traversal (Left - Right - Root)
public static void postorderTraversal(Node root) {
if (root == null)
return;
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.data + " ");
}
// Function for Level order tree traversal
public static void levelorderTraversal(Node root) {
if (root == null)
return;
// Queue for level order traversal
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
Node temp = q.poll();
System.out.print(temp.data + " ");
// Push left child in the queue
if (temp.left != null)
q.offer(temp.left);
// Push right child in the queue
if (temp.right != null)
q.offer(temp.right);
}
}
/* Driver function to check the above algorithm. */
public static void main(String[] args) {
Node root = null;
// Insertion of nodes
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
System.out.print("Preorder traversal: ");
preorderTraversal(root);
System.out.print("\nInorder traversal: ");
inorderTraversal(root);
System.out.print("\nPostorder traversal: ");
postorderTraversal(root);
System.out.print("\nLevel order traversal: ");
levelorderTraversal(root);
// Delete the node with data = 20
root = deletion(root, 20);
System.out.print("\nInorder traversal after deletion: ");
inorderTraversal(root);
}
}
from collections import deque
# Node class to define the structure of the node
class Node:
def __init__(self, val):
self.data = val
self.left = self.right = None
# Function to insert nodes
def insert(root, data):
# If tree is empty, new node becomes the root
if root is None:
root = Node(data)
return root
# Queue to traverse the tree and find the position to insert the node
q = deque()
q.append(root)
while q:
temp = q.popleft()
# Insert node as the left child of the parent node
if temp.left is None:
temp.left = Node(data)
break
# If the left child is not null push it to the queue
else:
q.append(temp.left)
# Insert node as the right child of parent node
if temp.right is None:
temp.right = Node(data)
break
# If the right child is not null push it to the queue
else:
q.append(temp.right)
return root
# Function to delete the given deepest node (d_node) in binary tree
def deletDeepest(root, d_node):
q = deque()
q.append(root)
# Do level order traversal until last node
while q:
temp = q.popleft()
if temp == d_node:
temp = None
del d_node
return
if temp.right:
if temp.right == d_node:
temp.right = None
del d_node
return
else:
q.append(temp.right)
if temp.left:
if temp.left == d_node:
temp.left = None
del d_node
return
else:
q.append(temp.left)
# Function to delete element in binary tree
def deletion(root, key):
if not root:
return None
if root.left is None and root.right is None:
if root.data == key:
return None
else:
return root
q = deque()
q.append(root)
temp = None
key_node = None
# Do level order traversal to find deepest node (temp) and node to be deleted (key_node)
while q:
temp = q.popleft()
if temp.data == key:
key_node = temp
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if key_node is not None:
x = temp.data
key_node.data = x
deletDeepest(root, temp)
return root
# Inorder tree traversal (Left - Root - Right)
def inorderTraversal(root):
if not root:
return
inorderTraversal(root.left)
print(root.data, end=" ")
inorderTraversal(root.right)
# Preorder tree traversal (Root - Left - Right)
def preorderTraversal(root):
if not root:
return
print(root.data, end=" ")
preorderTraversal(root.left)
preorderTraversal(root.right)
# Postorder tree traversal (Left - Right - Root)
def postorderTraversal(root):
if root is None:
return
postorderTraversal(root.left)
postorderTraversal(root.right)
print(root.data, end=" ")
# Function for Level order tree traversal
def levelorderTraversal(root):
if root is None:
return
# Queue for level order traversal
q = deque()
q.append(root)
while q:
temp = q.popleft()
print(temp.data, end=" ")
# Push left child in the queue
if temp.left:
q.append(temp.left)
# Push right child in the queue
if temp.right:
q.append(temp.right)
# Driver function to check the above algorithm
if __name__ == "__main__":
root = None
# Insertion of nodes
root = insert(root, 10)
root = insert(root, 20)
root = insert(root, 30)
root = insert(root, 40)
print("Preorder traversal:", end=" ")
preorderTraversal(root)
print("\nInorder traversal:", end=" ")
inorderTraversal(root)
print("\nPostorder traversal:", end=" ")
postorderTraversal(root)
print("\nLevel order traversal:", end=" ")
levelorderTraversal(root)
# Delete the node with data = 20
root = deletion(root, 20)
print("\nInorder traversal after deletion:", end=" ")
inorderTraversal(root)
using System;
using System.Collections.Generic;
// Node class to define the structure of the node
public class Node
{
public int data;
public Node left, right;
// Parameterized Constructor
public Node(int val)
{
data = val;
left = right = null;
}
}
public class Program
{
// Function to insert nodes
public static Node Insert(Node root, int data)
{
// If tree is empty, new node becomes the root
if (root == null)
{
root = new Node(data);
return root;
}
// Queue to traverse the tree and find the position to insert the node
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count != 0)
{
Node temp = q.Dequeue();
// Insert node as the left child of the parent node
if (temp.left == null)
{
temp.left = new Node(data);
break;
}
// If the left child is not null, push it to the queue
else
q.Enqueue(temp.left);
// Insert node as the right child of parent node
if (temp.right == null)
{
temp.right = new Node(data);
break;
}
// If the right child is not null, push it to the queue
else
q.Enqueue(temp.right);
}
return root;
}
/* function to delete the given deepest node (d_node) in binary tree */
public static void DeleteDeepest(Node root, Node d_node)
{
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
// Do level order traversal until last node
Node temp;
while (q.Count != 0)
{
temp = q.Dequeue();
if (temp == d_node)
{
temp = null;
d_node = null;
return;
}
if (temp.right != null)
{
if (temp.right == d_node)
{
temp.right = null;
d_node = null;
return;
}
else
q.Enqueue(temp.right);
}
if (temp.left != null)
{
if (temp.left == d_node)
{
temp.left = null;
d_node = null;
return;
}
else
q.Enqueue(temp.left);
}
}
}
/* function to delete element in binary tree */
public static Node Deletion(Node root, int key)
{
if (root == null)
return null;
if (root.left == null && root.right == null)
{
if (root.data == key)
return null;
else
return root;
}
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
Node temp = new Node(0);
Node key_node = null;
// Do level order traversal to find deepest node (temp) and node to be deleted (key_node)
while (q.Count != 0)
{
temp = q.Dequeue();
if (temp.data == key)
key_node = temp;
if (temp.left != null)
q.Enqueue(temp.left);
if (temp.right != null)
q.Enqueue(temp.right);
}
if (key_node != null)
{
int x = temp.data;
key_node.data = x;
DeleteDeepest(root, temp);
}
return root;
}
// Inorder tree traversal (Left - Root - Right)
public static void InorderTraversal(Node root)
{
if (root == null)
return;
InorderTraversal(root.left);
Console.Write(root.data + " ");
InorderTraversal(root.right);
}
// Preorder tree traversal (Root - Left - Right)
public static void PreorderTraversal(Node root)
{
if (root == null)
return;
Console.Write(root.data + " ");
PreorderTraversal(root.left);
PreorderTraversal(root.right);
}
// Postorder tree traversal (Left - Right - Root)
public static void PostorderTraversal(Node root)
{
if (root == null)
return;
PostorderTraversal(root.left);
PostorderTraversal(root.right);
Console.Write(root.data + " ");
}
// Function for Level order tree traversal
public static void LevelorderTraversal(Node root)
{
if (root == null)
return;
// Queue for level order traversal
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count != 0)
{
Node temp = q.Dequeue();
Console.Write(temp.data + " ");
// Push left child in the queue
if (temp.left != null)
q.Enqueue(temp.left);
// Push right child in the queue
if (temp.right != null)
q.Enqueue(temp.right);
}
}
/* Driver function to check the above algorithm. */
public static void Main(string[] args)
{
Node root = null;
// Insertion of nodes
root = Insert(root, 10);
root = Insert(root, 20);
root = Insert(root, 30);
root = Insert(root, 40);
Console.Write("Preorder traversal: ");
PreorderTraversal(root);
Console.Write("\nInorder traversal: ");
InorderTraversal(root);
Console.Write("\nPostorder traversal: ");
PostorderTraversal(root);
Console.Write("\nLevel order traversal: ");
LevelorderTraversal(root);
// Delete the node with data = 20
root = Deletion(root, 20);
Console.Write("\nInorder traversal after deletion: ");
InorderTraversal(root);
}
}
// Node class to define the structure of the node
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// Function to insert nodes
function insert(root, data) {
// If tree is empty, new node becomes the root
if (root === null) {
root = new Node(data);
return root;
}
// queue to traverse the tree and find the position to
// insert the node
const q = [];
q.push(root);
while (q.length !== 0) {
const temp = q.shift();
// Insert node as the left child of the parent node
if (temp.left === null) {
temp.left = new Node(data);
break;
}
// If the left child is not null push it to the
// queue
else
q.push(temp.left);
// Insert node as the right child of parent node
if (temp.right === null) {
temp.right = new Node(data);
break;
}
// If the right child is not null push it to the
// queue
else
q.push(temp.right);
}
return root;
}
/* function to delete the given deepest node
(d_node) in binary tree */
function deletDeepest(root, d_node) {
const q = [];
q.push(root);
// Do level order traversal until last node
let temp;
while (q.length !== 0) {
temp = q.shift();
if (temp === d_node) {
temp = null;
delete d_node;
return;
}
if (temp.right) {
if (temp.right === d_node) {
temp.right = null;
delete d_node;
return;
}
else
q.push(temp.right);
}
if (temp.left) {
if (temp.left === d_node) {
temp.left = null;
delete d_node;
return;
}
else
q.push(temp.left);
}
}
}
/* function to delete element in binary tree */
function deletion(root, key) {
if (!root)
return null;
if (root.left === null && root.right === null) {
if (root.data === key)
return null;
else
return root;
}
const q = [];
q.push(root);
let temp;
let key_node = null;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (q.length !== 0) {
temp = q.shift();
if (temp.data === key)
key_node = temp;
if (temp.left)
q.push(temp.left);
if (temp.right)
q.push(temp.right);
}
if (key_node !== null) {
const x = temp.data;
key_node.data = x;
deletDeepest(root, temp);
}
return root;
}
// Inorder tree traversal (Left - Root - Right)
function inorderTraversal(root) {
if (!root)
return;
inorderTraversal(root.left);
console.log(root.data + " ");
inorderTraversal(root.right);
}
// Preorder tree traversal (Root - Left - Right)
function preorderTraversal(root) {
if (!root)
return;
console.log(root.data + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
// Postorder tree traversal (Left - Right - Root)
function postorderTraversal(root) {
if (root === null)
return;
postorderTraversal(root.left);
postorderTraversal(root.right);
console.log(root.data + " ");
}
// Function for Level order tree traversal
function levelorderTraversal(root) {
if (root === null)
return;
// Queue for level order traversal
const q = [];
q.push(root);
while (q.length !== 0) {
const temp = q.shift();
console.log(temp.data + " ");
// Push left child in the queue
if (temp.left)
q.push(temp.left);
// Push right child in the queue
if (temp.right)
q.push(temp.right);
}
}
/* Driver function to check the above algorithm. */
let root = null;
// Insertion of nodes
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
console.log("Preorder traversal: ");
preorderTraversal(root);
console.log("\nInorder traversal: ");
inorderTraversal(root);
console.log("\nPostorder traversal: ");
postorderTraversal(root);
console.log("\nLevel order traversal: ");
levelorderTraversal(root);
// Delete the node with data = 20
root = deletion(root, 20);
console.log("\nInorder traversal after deletion: ");
inorderTraversal(root);
#include <bits/stdc++.h>
using namespace std;
// Node class to define the structure of the node
class Node {
public:
int data;
Node *left, *right;
// Parameterized Constructor
Node(int val)
{
data = val;
left = right = NULL;
}
};
// Function to insert nodes
Node* insert(Node* root, int data)
{
// If tree is empty, new node becomes the root
if (root == NULL) {
root = new Node(data);
return root;
}
// queue to traverse the tree and find the position to
// insert the node
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
// Insert node as the left child of the parent node
if (temp->left == NULL) {
temp->left = new Node(data);
break;
}
// If the left child is not null push it to the
// queue
else
q.push(temp->left);
// Insert node as the right child of parent node
if (temp->right == NULL) {
temp->right = new Node(data);
break;
}
// If the right child is not null push it to the
// queue
else
q.push(temp->right);
}
return root;
}
/* function to delete the given deepest node
(d_node) in binary tree */
void deletDeepest(Node* root, Node* d_node)
{
queue<Node*> q;
q.push(root);
// Do level order traversal until last node
Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == d_node) {
temp = NULL;
delete (d_node);
return;
}
if (temp->right) {
if (temp->right == d_node) {
temp->right = NULL;
delete (d_node);
return;
}
else
q.push(temp->right);
}
if (temp->left) {
if (temp->left == d_node) {
temp->left = NULL;
delete (d_node);
return;
}
else
q.push(temp->left);
}
}
}
/* function to delete element in binary tree */
Node* deletion(Node* root, int key)
{
if (!root)
return NULL;
if (root->left == NULL && root->right == NULL) {
if (root->data == key)
return NULL;
else
return root;
}
queue<Node*> q;
q.push(root);
Node* temp;
Node* key_node = NULL;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == key)
key_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
if (key_node != NULL) {
int x = temp->data;
key_node->data = x;
deletDeepest(root, temp);
}
return root;
}
// Inorder tree traversal (Left - Root - Right)
void inorderTraversal(Node* root)
{
if (!root)
return;
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
// Preorder tree traversal (Root - Left - Right)
void preorderTraversal(Node* root)
{
if (!root)
return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Postorder tree traversal (Left - Right - Root)
void postorderTraversal(Node* root)
{
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
// Function for Level order tree traversal
void levelorderTraversal(Node* root)
{
if (root == NULL)
return;
// Queue for level order traversal
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
cout << temp->data << " ";
// Push left child in the queue
if (temp->left)
q.push(temp->left);
// Push right child in the queue
if (temp->right)
q.push(temp->right);
}
}
/* Driver function to check the above algorithm. */
int main()
{
Node* root = NULL;
// Insertion of nodes
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << "\nInorder traversal: ";
inorderTraversal(root);
cout << "\nPostorder traversal: ";
postorderTraversal(root);
cout << "\nLevel order traversal: ";
levelorderTraversal(root);
// Delete the node with data = 20
root = deletion(root, 20);
cout << "\nInorder traversal after deletion: ";
inorderTraversal(root);
}
Output
Preorder traversal: 10 20 40 30 Inorder traversal: 40 20 10 30 Postorder traversal: 40 20 30 10 Level order traversal: 10 20 30 40 Inorder traversal after deletion: 40 10 30
Introduction to Binary Tree – Data Structure and Algorithm Tutorials
Binary Tree is a non-linear data structure where each node has at most two children. In this article, we will cover all the basics of Binary Tree, Operations on Binary Tree, its implementation, advantages, disadvantages which will help you solve all the problems based on Binary Tree.
Table of Content
- What is Binary Tree?
- Representation of Binary Tree
- Types of Binary Tree
- Operations On Binary Tree
- Insertion in Binary Tree
- Traversal of Binary Tree
- Deletion in Binary Tree
- Searching in Binary Tree
- Auxiliary Operations On Binary Tree
- Implementation of Binary Tree
- Complexity Analysis of Binary Tree Operations
- Advantages of Binary Tree
- Disadvantages of Binary Tree
- Applications of Binary Tree
- Frequently Asked Questions on Binary Tree