Answer to Question #40277 in C++ for estelle

Question

How can I find the maximum value in a binary tree using a recursive function? thanks

Answer 1

#include <stdlib.h>
#include <iostream>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct TreeNode
{
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
int data;
TreeNode* left;
TreeNode* right;
};

/* Give a binary tree and a number,
inserts a new TreeNode with the given number in
the random place in the end of the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
TreeNode* insertRandomly(TreeNode* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(new TreeNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (rand() % 2)
node->left = insertRandomly(node->left, data);
else
node->right = insertRandomly(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Given a non-empty binary search tree and current min value,
return the minimum data value found in that
tree. Recursion function */
int minValueHelper(TreeNode* node, int min);

/* Given a non-empty binary search tree return the minimum data value found in that
tree. */
int minValue(TreeNode* node) {
return minValueHelper(node, node->data);
}
int minValueHelper(TreeNode* node, int min)
{
if (node == NULL)
return min;
if (node->data < min)
min = node->data;
if (node->left != NULL && node->left->data < min)
min = node->left->data;
if (node->right != NULL && node->right->data < min)
min = node->right->data;
min = minValueHelper(node->left, min);
min = minValueHelper(node->right, min);
return min;
}

/* Driver program to test minValue function*/
int main()
{
TreeNode* root = NULL;
root = insertRandomly(root, 4);
insertRandomly(root, 2);
insertRandomly(root, -1);
insertRandomly(root, 3);
insertRandomly(root, 6);
insertRandomly(root, -5);
insertRandomly(root, -9);
insertRandomly(root, 0);
std::cout << "\n Minimum value in binary tree is " << minValue(root) << std::endl;
return 0;
}