Getting a max value from a Binary Tree

Question

Right now I binary tree and i want to get the max value out of it. Considering how it has both string and int values, it is ordered by alphabetical order. Everything is working properly all the inserts, search, delete etc. For now all we need to know is that here I have my tree.

typedef struct node 
{
    char *name;
    int count;
    struct node *l, *r; 
}*link;

How can I make a simple function that finds what is the highest count in the tree. Like I can have 20 nodes in the tree and suppose the highest count is 10 and there are 3 nodes with the highest count. It doesn't matter how many there are with 10 the highest count, I just want the function to return 10. A function like.

int maxValue(link head)
{
    //the help i need with
}

I've looked up online and tried some examples like the inorder and all of the different funtions but most of them just placed all values from left node to the most right one in order so it didnt really help me find the maximum number in the tree because mine is not organized from smallest to largest numbers.

Answer 1

The idea is to first compute the max values of the subtrees, maxLeft and maxRight, of a given node, and then return max(currVal, maxLeft, maxRight), where currVal is the value in the current node.

Here's how you express this directly in code:

int maxValue(link head)
{
    assert(head != NULL);
    int currVal = head->count;
    if (head->l != NULL) // compute max of the left subtree
        currVal = max(currVal, maxValue(head->l));
    if (head->r != NULL) // compute max of the right subtree
        currVal = max(currVal, maxValue(head->r));
    return currVal;
}

The max could be a simple macro, for example

#define max(x, y) (x) > (y) ? (x) : (y)

Answer 2

Recursion is your friend in this case. Your function compares the value of itself, the max of the left side and the max of the right side and returns the biggest value.

int maxValue(link head)
{
    if(head == NULL){
        return -1;
    }
    int me = head->count;
    int l = maxValue(head->l);
    int r = maxValue(head->r);
    if(me >= l && me >= r) {
        return me;
    } else if(l >= me && l >= r){
        return l;
    } else {
        return r;
    }
}

Remark

This code is not as general as one could have written it. It will only work as expected if count is always greater equals zero in the tree and if the function is not called on a NULL object in the beginning, since then -1 would be returned. Better use @blazs solution in practice.

Answer 3

To find the maximum value in a tree, code can not take advantage of alphabetical ordering. Instead the entire tree needs to be walked. This involves checking the current node and also then the max of each of the two children, left and right.

A classic improvement to walking a binary tree is to only recuse on one leg (e.g. left side) and loop on the other (right). This loop unrolling can sometimes be identified by a smart compiler that recurses on both legs. Here, below, it is done explicitly.

This code returns INT_MIN should the original head == NULL.

int maxValue(link head) {
  int max = INT_MIN;
  while (head) {
    if (head.count > max) {
      max = head.count;
    }
    int left_max = maxValue(head.left);
    if (left_max > max) { 
      max = left_max;
    }
    head = head.right;
  }
  return max;
}

Style: I'd rather see a typedef without the * as in below.

typedef struct node {
    char *name;
    int count;
    struct node *l, *r; 
} link;