Answer to Question #258524 in C for xyz

Question

Write the following menu driven program for the binary tree

----------------------------------------

Binary Tree Menu

----------------------------------------

1. Create

2. In-Order Traversal

3. Pre-Order Traversal

4. Post-Order traversal

5. Search

6. Find Smallest Element

7. Find Largest Element

8. Quit

Answer 1

#include <bits/stdc++.h>
using namespace std;
class node {
public:
	int dt;
	node* lt;
	node* rt;
};


node* newNode(int dt)
{
	node* t = new node();
	t->dt = dt;
	t->lt = t->rt = NULL;
	return t;
}


node* construct_tree_util(int pr[], int* pr_index, int lw,int hg, int n)
{
	if (*pr_index >= n || lw > hg)
		return NULL;
	node* root = newNode(pr[*pr_index]);
	*pr_index = *pr_index + 1;
	if (lw == hg)
		return root;
	int i;
	for (i = lw; i <= hg; ++i)
		if (pr[i] > root->dt)
			break;
	root->lt = construct_tree_util(pr, pr_index, *pr_index,i - 1, n);
	root->rt
		= construct_tree_util(pr, pr_index, i, hg, n);


	return root;
}


node* construct_tree(int pr[], int n)
{
	int pr_index = 0;
	return construct_tree_util(pr, &pr_index, 0, n - 1,n);
}


void display(node* node)
{
	if (node == NULL)
		return;
	display(node->lt);
	cout << node->dt << " ";
	display(node->rt);
}




int main()
{
	int pr[] = { 23,45,34,12,13,67,98,34};
	int n = sizeof(pr) / sizeof(pr[0]);


	node* root = construct_tree(pr, n);


	cout << "Inorder traversal of the constructed tree: \n";
	display(root);


	return 0;
}