5
\$\begingroup\$

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?

\$\endgroup\$
  • 3
    \$\begingroup\$ 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.) \$\endgroup\$ – GargantuChet Dec 1 '14 at 19:08
  • \$\begingroup\$ Can we assume that the tree is sorted? \$\endgroup\$ – GargantuChet Dec 1 '14 at 19:09
  • \$\begingroup\$ @GargantuChet Don't assume the tree's sorted. \$\endgroup\$ – user6607 Dec 1 '14 at 19:09
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – apnorton Dec 1 '14 at 22:51
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – user6607 Dec 2 '14 at 1:06
10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – GargantuChet Dec 5 '14 at 16:41
  • \$\begingroup\$ 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). \$\endgroup\$ – user6607 Dec 16 '14 at 16:37
  • \$\begingroup\$ 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. \$\endgroup\$ – GargantuChet Dec 16 '14 at 21:05
  • \$\begingroup\$ 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. \$\endgroup\$ – GargantuChet Dec 16 '14 at 21:12
  • \$\begingroup\$ 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. \$\endgroup\$ – CiaPan Jan 18 '17 at 19:40
4
\$\begingroup\$

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)));
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – GargantuChet Jan 19 '17 at 0:26
-3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – Cody Gray Jan 18 '17 at 17:59
  • \$\begingroup\$ @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. \$\endgroup\$ – CiaPan Jan 18 '17 at 19:20
  • \$\begingroup\$ 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. \$\endgroup\$ – Cody Gray Jan 18 '17 at 19:21
  • \$\begingroup\$ @CodyGray Oh, really...? \$\endgroup\$ – CiaPan Jan 18 '17 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.