if i have a binary tree such

            3
          /   \
         7     8
        / \   / \
       2   3 4   6 

I made a program to find the maximum value on the binary tree

int max_val(node *head){
    
    int leftmax, rightmax;

    int max = head->val;

    if (head->left != NULL) {
        leftmax = max_val(head->left);
        max = (max > leftmax) ? max : leftmax;
    }

    if (head->right != NULL) {
        rightmax = max_val(head->right);
        max = (max > rightmax) ? max : rightmax;
    }

    return max;

along with all the structs and stuff.

However this program will return 8 as 8 is the biggest value in the tree. Is there any way to limit the comparisons to only leaf nodes (so between 2, 3, 4, 6) and make it return 6 instead?

CodePudding user response：

The head node either has no subtrees, 1 subtree, or 2 subtrees.

if it has no subtrees, the associated value is the max.
if it has 1 subtree, the max is the max of that subtree.
if it has 2 subtrees, the max is the largest value among the max's in the subtrees.

CodePudding user response：

You should check all the leaves and the find the max there.

You can modify your code like this:

int max_val(node *head){
    if (head->left == null && head->right == null)
        return head->val;

    left = -∞;
    if (head->left!= null)
        left = max_val(*head->left);

    right = -∞;
    if (head->right != null)
        right = max_val(*head->right);

    return left > right ? left : right;
}