CODEWITHSUNDEEP
javasearchrecursiontreebinary-tree
NoobEditor
NoobEditor

Reputation: 15921

Find maximum element in binary tree

I am really confused about finding an element in a binary tree.

Question: When we say, search an element in a binary tree, maximum, in this case, do we assume that the tree is sorted???

If not, take a look at the below code, I got it from a book and almost every online URL suggests a similar pattern

int FindMaxNmb(BinaryTreeNode root)
{
    int root_val, left, right, max;
    if(root != null)
    {
        root_val = root.getData();
        
        //recursion - this is what I don't understand
            
        /*
        * This code would have made sense if the binary tree contained
        * Sorted elements, like  The left subtree of a node contained 
        * Only nodes with keys less than the node's key The right subtree 
        * of a node contained only nodes with keys greater 
        * than the node's key.  
        * */

        left = FindMaxNmb(root.getLeft());
        right = FindMaxNmb(root.getRight());
            
        //Find max number
        if(left > right)
        {
            max = left;
        }
        else
        {
            max = right;
        }
    
        if(root_val > max)
        {
            max = root_val;
        }
    }
    return max;
}

What i don't understand : take this recursion for instance left = FindMaxNmb(root.getLeft()); this will go on calling unless it reaches the leftmost bottom leaf and then assigns the value, same is with getRight()....but this thing only works for the leftmost node having 2 children...how does it check the value of remaining nodes (I am assuming that binary tree is not sorted)

I know I am missing something very obvious here...please help!!

Upvotes: 4

Views: 7695

Answers (1)

user2864740
user2864740

Reputation: 62005

The difference between a Binary Tree and Binary Search Tree is that a BST has a guaranteed between each node and its left/right child nodes - a plain BT has no ordering.

The code presented will work for a plain Binary Tree because it traverses all nodes in a depth first manner. (If the data was a BST the algorithm would only need to find the "rightmost" node and return it's value to find the maximum value in the tree.)

Now, in the BT implementation shown, each recursive function finds the maximum value of the sub-tree given by the left or right child node (the child node is root of the sub-tree) and it is this value that is returned.

For instance, consider this Binary Tree, which is not a BST in this case (from Wikipedia):

http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/192px-Binary_tree.svg.png

The call stack, as it works the way through the tree, will look like the following where - represents a stack level and the number represents the node.

-2
--7 (l)
---2 (l)
---6 (r)
----5 (l)
----11 (r)
--5 (r)
---9 (r)
----4 (l)

The stack can only "unwind" when it reaches the terminal case - this after the maximum value of the left and right sub-trees has been computed (via recursion into FindMaxNmb).

On the unwinding phase ..

  • .. when node 11 is reached there is no right node so it returns to 6
  • since this finishes searching in the right sub-tree (of 6) it returns to 7
  • since this finishes searching in the right sub-tree (of 7) it returns to 2
  • since this finishes searching in the left sub-tree (of 2), the right sub-tree (5) is entered ..

Upvotes: 2

Related Questions