Finding the maximum value in a binary tree

Question

I have to find the maximum value in a binary tree. This is how I did it iteratively:

int maxValue(Node* node)
{
 if (node == nullptr)
 throw "BT is empty";
 int max = node->data;
 for (Node* left = node; left != nullptr; left = left->left)
 {
 if (left->data > max)
 max = left->data;
 }
 for (Node* right = node; right != nullptr; right = right->right)
 {
 if (right->data > max)
 max = right->data;
 }
 return max;
}

I don't know if this is the best way to do it. How can this be improved? Is there a recursive solution?

• GargantuChet: The first approach treats the left and right sides as linked lists -- it doesn't check the left node's right child, or the right node's left child. I would expect that the second approach would always return INT_MAX, since neither of the if statements could be true. (max is initially INT_MAX, and if the data field is an int, it's not possible for the value of data to be more than max already is.)
• GargantuChet: Can we assume that the tree is sorted?
• user6607: @GargantuChet Don't assume the tree's sorted.
• apnorton: Quick question: why is this a CR question, and not an SO question? This code is "buggy", since it wouldn't find the max value if it were contained in 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).
• user6607: @anorton Since I was asking if it could be improved I thought it would be better on CR. I didn't know the code was buggy until GargantuChet commented.

Answer 1

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.

• GargantuChet: I'm not sure that I follow Loki Astari's edit -- it replaces a null check on each recursive call with a null check on each recursive call, and it adds unnecessary information to the call stack (currentMax). And on the leaf nodes it extends the call one level deeper than the original. Since I don't know the site's conventions I'll leave the edit, but wanted to add my thoughts on it.
• user6607: What do you mean by "it replaces a null check on each recursive call with a null check on each recursive call"? Also, I'm not sure how currentMax is unnecessary information, it's the same as max in your original example (btw you didn't define max anywhere in your example).
• GargantuChet: Thanks -- fixed the missing declaration, as it was unintentional. And I'm wrong, as either way the variable would be on the stack (local variable vs. argument to call), so it's probably a wash there.
• GargantuChet: Wow, I really did overlook the point of the edit. It keeps one null check per node -- but my original code would check twice. Loki Astari's edit reduces the number of null checks. On a largish tree, it's pretty certain that the branch prediction will cause "if (node == nullptr)" to settle on "false" as a default path pretty quickly. But it's still a valid alternate approach, to eliminate the extra check altogether.
• CiaPan: Please note that N nodes have 2N pointers to children nodes, so a half of left and right pointers are NULL. Clearly, all those pointers must be tested, whether we test for node == NULL inside the function or for left and right being NULL before diving into the recursion. However, testing before the call saves us N of 2N calls at the expense of additional if() instruction.

Answer 2

With most issues already mentioned, here is a simpler version of the code mentioned by GargantuChet. A recursive call to return the maximum value in a binary tree.

int getMax(Node* root){
 if(root==NULL){
 return Integer.MIN_VALUE; // the minimum value so that it does not affect the calculation
 }
 // return the maximum of the data of the current node ,its left child and its right child.
 return Math.max(root->data, Math.max(getMax(root->left), getMax(root->right)));
}

• GargantuChet: Nice. It doesn't properly handle the case where root = null, although you could easily just say that the behavior of getMax(null) is undefined.

Answer 3

why do you search left side of the tree, no need just one for loop enough since you are searching for Max number.

• Cody Gray: Can you expand this into a more complete answer by explaining why it is not necessary to search the left side, and maybe showing an example of what the new code would look like?
• CiaPan: @CodyGray I suppose Seham Ali assumed you have a BST, in which case the maximum value is stored in the rightmost node of a tree.
• Cody Gray: The point was to improve the answer, @cia. I personally know how a binary search tree works, but it isn't from reading this answer.
• CiaPan: @CodyGray Oh, really...?