Insertion in binary search tree using recursion in c++

C++ program for Insertion in binary search tree using recursion. Here more information.

// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Insertion in binary search tree by using recursion
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = nullptr;
		this->right = nullptr;
	}
};
class BinarySearchTree
{
	public: TreeNode *root;
	BinarySearchTree()
	{
		this->root = nullptr;
	}
	// Insert a node element
	TreeNode *addNode(TreeNode *node, int data)
	{
		if (node != nullptr)
		{
			if (node->data >= data)
			{
				// When new element is smaller or
				// equal to current node
				node->left = this->addNode(node->left, data);
			}
			else
			{
				// When new element is higher to current node
				node->right = this->addNode(node->right, data);
			}
			// important to manage root node
			return node;
		}
		else
		{
			return new TreeNode(data);
		}
	}
	// Display preorder
	void preorder(TreeNode *node)
	{
		if (node != nullptr)
		{
			// Display node value
			cout << "  " << node->data;
			// Visit to left subtree
			this->preorder(node->left);
			// Visit to right subtree
			this->preorder(node->right);
		}
	}
	void inorder(TreeNode *node)
	{
		if (node != nullptr)
		{
			// Visit to left subtree
			this->inorder(node->left);
			// Display node value
			cout << "  " << node->data;
			// Visit to right subtree
			this->inorder(node->right);
		}
	}
	void postorder(TreeNode *node)
	{
		if (node != nullptr)
		{
			// Visit to left subtree
			this->postorder(node->left);
			// Visit to right subtree
			this->postorder(node->right);
			// Display node value
			cout << "  " << node->data;
		}
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	/*
	         10
	        / \
	       /   \
	      4     15
	     / \   /
	    3   5 12
	    -------------
	    Build binary search tree
	*/
	tree->root = tree->addNode(tree->root, 10);
	tree->addNode(tree->root, 4);
	tree->addNode(tree->root, 3);
	tree->addNode(tree->root, 5);
	tree->addNode(tree->root, 15);
	tree->addNode(tree->root, 12);
	// Display tree nodes
	cout << "Preorder " << endl;
	tree->preorder(tree->root);
	cout << "\nInorder " << endl;
	tree->inorder(tree->root);
	cout << "\nPostorder " << endl;
	tree->postorder(tree->root);
	return 0;
}

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