Insertion in binary search tree using recursion in c

C program for Insertion in binary search tree using recursion. Here problem description and explanation.

// Include header file
#include <stdio.h>
#include <stdlib.h>

// C program for
// Insertion in binary search tree by using recursion
typedef struct TreeNode
{
	// Define useful field of TreeNode
	int data;
	struct TreeNode * left;
	struct TreeNode * right;
}TreeNode;

TreeNode * getTreeNode(int data)
{
	// Create dynamic memory of TreeNode
	TreeNode * ref = (TreeNode * ) malloc(sizeof(TreeNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->data = data;
	ref->left = NULL;
	ref->right = NULL;
	return ref;
}
typedef struct BinarySearchTree
{
	// Define useful field of BinarySearchTree
	struct TreeNode * root;
}BinarySearchTree;

BinarySearchTree * getBinarySearchTree()
{
	// Create dynamic memory of BinarySearchTree
	BinarySearchTree * ref = 
      (BinarySearchTree * ) malloc(sizeof(BinarySearchTree));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->root = NULL;
	return ref;
}
// Insert a node element
TreeNode * addNode(TreeNode * node, int data)
{
	if (node != NULL)
	{
		if (node->data >= data)
		{
			// When new element is smaller or
			// equal to current node
			node->left = addNode(node->left, data);
		}
		else
		{
			// When new element is higher to current node
			node->right = addNode(node->right, data);
		}
		// important to manage root node
		return node;
	}
	else
	{
		return getTreeNode(data);
	}
}
// Display preorder
void preorder(TreeNode * node)
{
	if (node != NULL)
	{
		// Display node value
		printf(" %d ", node->data);
		// Visit to left subtree
		preorder(node->left);
		// Visit to right subtree
		preorder(node->right);
	}
}
void inorder(TreeNode * node)
{
	if (node != NULL)
	{
		// Visit to left subtree
		inorder(node->left);
		// Display node value
		printf(" %d ", node->data);
		// Visit to right subtree
		inorder(node->right);
	}
}
void postorder(TreeNode * node)
{
	if (node != NULL)
	{
		// Visit to left subtree
		postorder(node->left);
		// Visit to right subtree
		postorder(node->right);
		// Display node value
		printf(" %d ", node->data);
	}
}
int main()
{
	BinarySearchTree * tree = getBinarySearchTree();
	/*
	         10
	        / \
	       /   \
	      4     15
	     / \   /
	    3   5 12
	    -------------
	    Build binary search tree
	*/
	tree->root = addNode(tree->root, 10);
	addNode(tree->root, 4);
	addNode(tree->root, 3);
	addNode(tree->root, 5);
	addNode(tree->root, 15);
	addNode(tree->root, 12);
	// Display tree nodes
	printf("Preorder \n");
	preorder(tree->root);
	printf("\nInorder \n");
	inorder(tree->root);
	printf("\nPostorder \n");
	postorder(tree->root);
}

Output

Preorder
 10  4  3  5  15  12
Inorder
 3  4  5  10  12  15
Postorder
 3  5  4  12  15  10


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved