Simple Binary Tree Program

Simple Binary Tree:

In this blog we will see, how to create a simple binary tree. We will be using Queue data structure to store the last node inserted in the tree. This will prevent unnecessary traversal of tree for each new node insertion.

Time Complexity: O(n)
Space Complexity: O(n)

	/*
	A Simple Binary Tree
	**/
	#include<iostream>
	#include<stdlib.h>
	using namespace std;
	/*
	defining the structure
	**/
	typedef struct Tree {
	int data;
	struct Tree *left, *right;
	}BTree;
	typedef struct Queue {
	int front, rear;
	int cap,size;
	BTree **arr;
	}Queue;
	/*
	* Utility methods for Queue
	*/
	Queue *initializeQueue (int size) {
	Queue *q = (Queue*) malloc (sizeof (Queue));
	q->front = q->rear = -1;
	q->cap = size;
	q->size = 0;
	q->arr = (BTree**) malloc (sizeof (BTree*) * size);
	if (!q->arr)
	return NULL;
	return q;
	}
	int isEmpty (Queue *q) {
	return q->front == -1;
	}
	int isFull (Queue *q) {
	return ((q->rear + 1) % q->cap == q->front);
	}
	void resizeQueue (Queue *q) {
	int size = q->cap * 2;
	q->cap = size;
	q->arr = (BTree**) realloc (q->arr, q->cap);
	if (!q->arr)
	return;
	if (q->front > q->rear) {
	for (int i = 0; i < q->front; i ++) {
	q->arr[i + size] = q->arr[i];
	}
	q->rear = q->rear + size;
	}
	}
	void enQueue (Queue *q, BTree *data) {
	if (isFull (q)) {
	cout<<"\nQueue is full. Increasing Queue size";
	resizeQueue (q);
	}
	q->rear = (q->rear + 1) % q->cap;
	q->arr[q->rear] = data;
	if (q->front == -1)
	q->front = q->rear;
	q->size ++;
	}
	BTree* deQueue (Queue *q) {
	if (isEmpty (q))
	return NULL;
	BTree* data = q->arr[q->front];
	if (q->front == q->rear)
	q->front = q->rear = -1;
	else
	q->front = (q->front + 1) % q->cap;
	q->size --;
	return data;
	}
	void deleteQueue (Queue *q) {
	if (q) {
	if (q->arr)
	free (q->arr);
	free (q);
	}
	}
	BTree* initializeNode () {
	BTree *root = (BTree*) malloc (sizeof (BTree));
	if (!root) return NULL;
	root->left = root->right = NULL;
	return root;
	}
	/*
	* Method Name: preOrder
	* Description: Prints preorder traversal of tree
	*/
	void preOrder (BTree *root) {
	if (root) {
	cout <<root->data<<" ";
	preOrder (root->left);
	preOrder (root->right);
	}
	}
	/*
	* Method Name: inOrder
	* Description: Prints inorder traversal of tree
	*/
	void inOrder (BTree *root) {
	if (root) {
	inOrder (root->left);
	cout <<root->data<<" ";
	inOrder (root->right);
	}
	}
	/*
	* Method Name: postOrder
	* Description: Prints post order traversal of tree
	*/
	void postOrder (BTree *root) {
	if (root) {
	postOrder (root->left);
	postOrder (root->right);
	cout <<root->data<<" ";
	}
	}
	/*
	* Method Name: insertNode
	* Description: Inserts data in a binary tree
	*/
	void insertNode (BTree **root) {
	Queue *q = initializeQueue (20);
	// 1. Elements we want to insert
	for (int i = 1; i < 10; i ++) {
	// 2. create an empty node
	BTree *node = initializeNode ();
	node->data = i;
	// 3. If tree is empty then make it as root
	if (*root == NULL)
	*root = node;
	else {
	// 4. get last inserted node and assign to left/right whichever is null
	BTree *front = q->arr[q->front];
	if (front->left == NULL) {
	front->left = node;
	} else if (front->right == NULL){
	front->right = node;
	}
	// 5. delete the front if its both child are not empty
	if (front->left && front->right){
	deQueue (q);
	}
	}
	// 6. Insert the newly created node
	enQueue (q, node);
	}
	// 7. Delete the queue
	deleteQueue (q);
	}
	int main (void) {
	BTree *root = NULL;
	insertNode (&root);
	cout<<"\nPreorder Traversal:";
	preOrder (root);
	cout<<"\nInorder Traversal:";
	inOrder (root);
	cout<<"\nPostOrder Traversal:";
	postOrder (root);
	cout<<endl;
	return 0;
	}
	/*
	Output:
	Preorder Traversal:1 2 4 8 9 5 3 6 7
	Inorder Traversal:8 4 9 2 5 1 6 3 7
	PostOrder Traversal:8 9 4 5 2 6 7 3 1
	*/

view raw binaryTree.cpp hosted with ❤ by GitHub