Trees are often most useful when they're sorted. If the tree is sorted, you can just descend into the right side of the tree.
Since we're assuming an unsorted tree, we have to search the whole thing. Let's build this up by cases. First assume that the current node has the largest value:
int maxValue(Node *node)
{
if (node == nullptr)
throw "BT is empty";
max = node->data;
return max;
}
Nice, but not likely. We can do better. What if the largest value is in the left side of the tree?
int maxValue(Node *node)
{
if (node == nullptr)
throw "BT is empty";
max = node->data;
if(node->left != nullptr) {
int leftMax = maxValue(node->left);
if(max < leftMax)
max = leftMax;
}
return max;
}
Great! Now we have a function that will check its left side for larger values, all the way down the left side. But what if the largest value is on the right of some node? We'd better cover that case too:
int maxValue(Node *node)
{
if (node == nullptr)
throw "BT is empty";
int max = node->data;
if(node->left != nullptr) {
int leftMax = maxValue(node->left);
if(max < leftMax)
max = leftMax;
}
if(node->right != nullptr) {
int rightMax = maxValue(node->right);
if(max < rightMax)
max = rightMax;
}
return max;
}
Now since we only have to check for NULL that will throw on the first node we can optimize slightly:
int maxValue(Node *node)
{
if (node == nullptr)
throw "BT is empty";
return maxValueNonNull(node, node->data);
}
int maxValueNonNull(Node* node, int currentMax)
{
if (node == NULL)
{ return currentMax;
}
currentMax = currentMax > node->data ? currentMax : node->data;
int leftMax = maxValueNonNull(node->left, currentMax);
int rightMax = maxValueNonNull(node->right, currentMax);
return leftMax > rightMax ? leftMax : rightMax;
}
That should do it.
max
is initiallyINT_MAX
, and if thedata
field is an int, it's not possible for the value ofdata
to be more thanmax
already is.) \$\endgroup\$node->left->right
. Also, the answer isn't really a review of the code, but rather a description of DFS applied to finding the maximum value in a tree (that's really why I ask). \$\endgroup\$