SimpleTreeDemo.cpp

#include <iostream>

using namespace std;

//============================================//
//              Tree Structure
//============================================//
struct node
{
	int data;   // data
	node *left; // left subtree
	node *right; // left subtree
};

node *root = NULL;  
//============================================//
// Minimal operations
bool lookup(struct node* node, int target);
node* createNode(int data);
node* insert(struct node* tree, int value);
void printTree(struct node* tree);
int getRoot(struct node* tree);
//============================================//



bool lookup(struct node* node, int target) {
	 // 1. Base case == empty tree
	 // in that case, the target is not found so return false
	 if (node == NULL) {
	 	return(false);
	 }
	 else {
		 // 2. see if found here
		 if (target == node->data) return(true);
		 else {
			 // 3. otherwise recur down the correct subtree
			 if (target < node->data) return(lookup(node->left, target));
			 else return(lookup(node->right, target));
		 }
	 }
}

node* createNode(int data) {
	 node* temp = new node; 
	 temp->data = data;
	 temp->left = NULL;
	 temp->right = NULL;
	 return(temp);
}

node* insert(struct node* tree, int value) {
	 // 1. If the tree is empty, return a new, single node
	 if (tree == NULL) {
	 	return(createNode(value));
	 }
	 else {
	 // 2. Otherwise, recur down the tree
	 if (value <= tree->data) 
	 	tree->left = insert(tree->left, value);
	 else 
	 	tree->right = insert(tree->right, value);
	 return(tree); // return the (unchanged) node pointer
	 }
}

void printTree(struct node* tree) {
	 if (tree == NULL) return;
	 printTree(tree->left);
	 cout << tree->data << " ";
	 printTree(tree->right);
}

int getRoot(struct node* tree){
	return (tree->data);
}

int main(){
	node* root = createNode(2);
 	root->left = createNode(1);
 	root->right = createNode(3);
 	printTree(root);
 	cout << "\nTree Root = " << getRoot(root) << endl;
 	cout << "lookup(root, 5) = " << lookup(root, 5) << endl;
 	insert(root, 5);
 	printTree(root);
 	cout << "\nlookup(root, 5) = " << lookup(root, 5) << endl;
 	return 0;
}