Hi, I am trying to implement a binary tree(not sorted) using recursion. I have figured out most of my function however GetMax and GetMin are confusing me.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef int TreeEntry;

typedef struct binary_tree_node {
	TreeEntry item;
	struct binary_tree_node * left;
	struct binary_tree_node * right;
} BinaryTreeNode;


BinaryTreeNode* CreateNode(TreeEntry entry);
void            DestroyTree(BinaryTreeNode* root);
void            PrintInOrder(BinaryTreeNode* root);
void            PrintPreOrder(BinaryTreeNode* root);
void            PrintPostOrder(BinaryTreeNode* root);
int             GetHeight(BinaryTreeNode* root);

void            PrintReverseOrder(BinaryTreeNode* root);
int             GetSize(BinaryTreeNode* root);
int             GetSum(BinaryTreeNode* root);
int             GetMax(BinaryTreeNode* root);
int             GetMin(BinaryTreeNode* root);

BinaryTreeNode* CreateSampleTree();

void            Error(const char* msg);


int main(void)
{
	BinaryTreeNode* tree = CreateSampleTree();

	printf("In Order:      ");  PrintInOrder(tree); printf("\n");
	printf("Reverse Order: ");  PrintReverseOrder(tree); printf("\n");

	printf("Height: %d\n", GetHeight(tree));
	printf("Size:   %d\n", GetSize(tree));
	printf("Sum:    %d\n", GetSum(tree));
	printf("Max:    %d\n", GetMax(tree));
	printf("Min:    %d\n", GetMin(tree));

	DestroyTree(tree);

	return 0;
}


void Error(const char* msg)
{
	printf("ERROR: %s\n", msg);
	exit(EXIT_FAILURE);
}


BinaryTreeNode* CreateNode(TreeEntry entry)
{
	BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	if (node == NULL)
		Error("Out of memory");
	node->item = entry;
	node->left = NULL;
	node->right = NULL;
	return node;
}


BinaryTreeNode* CreateSampleTree()
{
	BinaryTreeNode* root = NULL;
	BinaryTreeNode* parent = NULL;

	/* create root node and its children */

	root = CreateNode(2);
	root->left = CreateNode(7);
	root->right = CreateNode(5);

	/* construct the left subtree */

	parent = root->left;
	parent->left = CreateNode(3);
	parent->right = CreateNode(6);

	parent = parent->right;
	parent->left = CreateNode(5);
	parent->right = CreateNode(11);

	parent = parent->left;
	parent->left = CreateNode(1);

	/* construct the right subtree */

	parent = root->right;
	parent->right = CreateNode(9);

	parent = parent->right;
	parent->left = CreateNode(4);

	return root;
}


void PrintInOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintInOrder(root->left);
		printf("%d ", root->item);
		PrintInOrder(root->right);
	}
}


void PrintPreOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		printf("%d ", root->item);
		PrintPreOrder(root->left);
		PrintPreOrder(root->right);
	}
}


void PrintPostOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintPostOrder(root->left);
		PrintPostOrder(root->right);
		printf("%d ", root->item);
	}
}


void DestroyTree(BinaryTreeNode* root)
{
	if (root != NULL) {
		DestroyTree(root->left);
		DestroyTree(root->right);
		free(root);
	}
}


int GetHeight(BinaryTreeNode* root)
{
	if (root == NULL)
		return 0;
	else {
		int leftHeight = GetHeight(root->left);
		int rightHeight = GetHeight(root->right);

		if (leftHeight > rightHeight)
			return 1 + leftHeight;
		else
			return 1 + rightHeight;
	}
}

void PrintReverseOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintReverseOrder(root->right);
		printf("%d ", root->item);
		PrintReverseOrder(root->left);
	}
}

int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
		return 0;
	else {
		return(GetSize(root->left) + 1 + GetSize(root->right));
	}
}

int GetSum(BinaryTreeNode* root)
{
	if(root == NULL){
		return 0;
	}
	else{
		return(GetSum(root->left) + root->item + GetSum(root->right));
	}
}

/*
 * The functions below here are the ones I can't figure out.   
 */

int GetMax(BinaryTreeNode* root)
{
	int max;
	if(root == NULL){
		return INT_MIN;
	}
	else{
                return -1;
	}

}

int GetMin(BinaryTreeNode* root)
{
	if(root == NULL){
		return INT_MAX;
	}
	else{
		return -1;
	}
}

Right now they return -1 (so that i can compile and test the rest of the code while i was working on it) that needs to be replaced by the recursive code to find the max and min. Thanks for the help.

Edited 6 Years Ago by xxpokerxx: n/a

Never mind I figured it out, here is the code for the GetMax and GetMin function for anyone else who may need it.

int GetMax(BinaryTreeNode* root)
{
	int nodeItem, leftmax, rightmax, max;
	max = -1;
	
	if(root == NULL){
		return INT_MIN;
	}
	else{
		nodeItem = root->item;
		leftmax = GetMax(root->left);
		rightmax = GetMax(root->right);

	if (leftmax > rightmax)
		max = leftmax;
	else
		max = rightmax;
	if (nodeItem > max)
		max = nodeItem;
	}
	
return max;
}

int GetMin(BinaryTreeNode* root)
{
	int nodeItem, leftmax, rightmax, min;
	min = -1;
	
	if(root == NULL){
		return INT_MAX;
	}
	else{
		nodeItem = root->item;
		leftmax = GetMin(root->left);
		rightmax = GetMin(root->right);

	if (leftmax < rightmax)
		min = leftmax;
	else
		min = rightmax;
	if (nodeItem < min)
		min = nodeItem;
	}
	
return min;
}

Edited 6 Years Ago by xxpokerxx: n/a

This article has been dead for over six months. Start a new discussion instead.