CODEWITHSUNDEEP
c++binary-tree
Becca
Becca

Reputation: 11

C++ Finding largest number in binary tree

Binary tree of numbers, with a node structure

type def numbernode
{
    unsigned value;
    numbernode * left;
    numbernode * right;
}

and an external pointer (to the root node) write a function in largest (numbernode * tree) will return the largest number in the tree , if the tree is not empty. your function should return -1 if the tree is empty.

its a practice question for a test, i've spent hours trying to figure it out, i need some code assistance!!

Upvotes: 1

Views: 13015

Answers (5)

Dan F
Dan F

Reputation: 17732

Recursion problems are really easy to solve once you start thinking about them the right way, especially with regards to trees. "What is the largest number in the tree? Well its the highest of myself, my left child, and my right child...what is the highest of my left child? well its the highest of that child, its left, and its right...." and so on.

really simple recursion problem.

int largest( node* root )
{
    if ( root == null )
        return -1;

    int left = largest(root->left);
    int right = largest ( root->right);
    if( root->value > left && root->value > right )
       return root->value;
    else
       return max ( left, right );
}

Upvotes: 8

corsiKa
corsiKa

Reputation: 82559

recursion is your friend - here's the outline

int maxValue(Node n) {

    if(n == null) return -1 // if this is a null node, get out with -1

    // each time you call this, it spawns a new version of this function
    // calling maxValue(root) could end up calling maxValue on a .left node
    // dozens of times before it calls one on a .right node!
    int left = maxValue(n.left) // get the left value's max
    int right = maxValue(n.right) // get the right value's max

    return max(this.value, left, right) // return the highest of the three values
}

this is the basic idea. You go down the children of the current node, and get the result back, see if their results are better than yours. The highest value will work its way up the chain.

P.S. the syntax in my code is simply wrong. For instance, there's no semi-colons. It also ignores pointers or anything. Think of it as C++ friendly pseudo-code only.

Upvotes: 5

Shamim Hafiz - MSFT
Shamim Hafiz - MSFT

Reputation: 22064

Just do a traversal of the tree using any of the known method of inorder, preorder or postorder. You are bound to encounter the largest element during the traversal.

Upvotes: 2

sehe
sehe

Reputation: 392883

Do you know the tree traversal algorithms (in-order, pre-order, post-order)?

Draw a simple tree, and do the steps with you pencil. At some point in a subtree, try to 'generalize' a description that works for the subtree, and then see if you can come up with a description that would 'keep' working for the whole tree.

Upvotes: 0

Kevin Hsu
Kevin Hsu

Reputation: 1756

Just walk the right side of the tree and return the last non-null node.

Upvotes: 0

Related Questions