current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
2  
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 yesterday
    
Can we assume that the tree is sorted? –  GargantuChet yesterday
    
@GargantuChet Don't assume the tree's sorted. –  user6607 yesterday
    
@GargantuChet +1 "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" –  MORTAL yesterday
    
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). –  anorton yesterday

1 Answer 1

up vote 5 down vote accepted

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

    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.

share|improve this answer
    
Thanks for showing me the steps. I get it now. Thanks! –  user6607 yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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