Question #40277

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

Expert's answer

#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;

}

#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;

}

## Comments

## Leave a comment