Skip to main content
Code Review

Return to Answer

declared max
Source Link
GargantuChet
GargantuChet
  • 226
  • 2
  • 5
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;
}

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

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;
}
added 674 characters in body
Source Link
Loki Astari
Loki Astari
  • 97.7k
  • 5
  • 126
  • 341

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.

That should do it.

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.

Source Link
GargantuChet
GargantuChet
  • 226
  • 2
  • 5

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

That should do it.