Insertion in binary search tree without recursion in c

C program for Insertion in binary search tree without recursion. Here problem description and other solutions.

// Include header file
#include <stdio.h>
#include <stdlib.h>
// C program for
// iterative insert in binary search tree
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 element
void addNode(BinarySearchTree * ref, int data)
{
	// Create a new node
	TreeNode * node = getTreeNode(data);
	if (ref->root == NULL)
	{
		// When adds a first node in bst
		ref->root = node;
	}
	else
	{
		TreeNode * find = ref->root;
		// Add new node to proper position
		while (find != NULL)
		{
			if (find->data >= data)
			{
				if (find->left == NULL)
				{
					// When left child empty
					// So add new node here
					find->left = node;
					return;
				}
				else
				{
					// Otherwise
					// Visit left sub-tree
					find = find->left;
				}
			}
			else
			{
				if (find->right == NULL)
				{
					// When right child empty
					// So add new node here
					find->right = node;
					return;
				}
				else
				{
					// Visit right sub-tree
					find = find->right;
				}
			}
		}
	}
}
// 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

	*/
	addNode(tree, 10);
	addNode(tree, 4);
	addNode(tree, 3);
	addNode(tree, 5);
	addNode(tree, 15);
	addNode(tree, 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