minimum element of binary tree

Question

I have implemented functions to find the max and min element of the binary tree. But I am getting the wrong output for it.

Function to find the maximum of the binary tree.

int FindMax(struct TreeNode *bt)
{
//get the maximum value of the binary tree... 
int max;
//get the maximum of the left sub-tree. 
int left;
//get the maximum of the right sub-tree.
int right;
//get the root of the current node.
int root;

        if(bt!=NULL)
        {

                root=bt->data;
                //Call the left tree recursively....
                left=FindMax(bt->leftChild);

                //Call the right tree recursively...
                right=FindMax(bt->rightChild);

                if(left > right)
                {
                        max=left;
                }
                else
                {
                        max=right;
                }
                if(max < root)
                {
                        max=root;
                }

        }

return max;
}

Function to find the min of binary tree.

int FindMin(struct TreeNode *bt)
{
//get the minimum value of the binary tree... 
int min;
//get the minimum of the left sub-tree. 
int left;
//get the minimum of the right sub-tree.
int right;
//get the root of the current node.
int root;
        if(bt!=NULL)
        {

                root=bt->data;
                //Call the left tree recursively....
                left=FindMin(bt->leftChild);

                //Call the right tree recursively...
                right=FindMin(bt->rightChild);

                if(left < right)
                {
                        min=left;
                }
                else
                {
                        min=right;
                }
                if(min > root)
                {
                        min=root;
                }

        }

return min;
}

Output : The maximum of tree 32767

The minimum of tree 0

Answer 1

One way to do it (in C) using recursion:

In main:

printf("maximum (not BST) is: %d\n", FindMax(root, root->x));

The Function:

int FindMax(node *root, int max)
{
    if(root->x > max) max = root->x;
    if(root->left != NULL)
        max = FindMax(root->left, max);
    if(root->right != NULL )
        max = FindMax(root->right, max);
    return max; 
}

Notice that here you have to pass the original root value when you first call the function, and then everytime pass the current maximum. You do not go into the function for empty nodes, and you don't create any new variables in the function itself.

The implementation of "ravi ranjan" only in c: in main:

printf("minimum (not BST) %d\n", FindMin(root));

the function:

int FindMin(node *root)
{
    int min = root->x;
    int tmp;
    if(root->left != NULL)
    {
        tmp = FindMin(root->left);
        min = (min < tmp) ? min : tmp;
    }    
    if(root->right != NULL)
    {
        tmp = FindMin(root->right);
        min = (min < tmp) ? min : tmp;

    }    
    return min; 
}

Notice here you do create a local variable (much like the passed value in the previous example) and you also need to create a tmp variable for ease of use and readability. (or define a minimum macro beforehand).

Answer 2

private int minElem(Node node) {
    int min= node.element;
    if(node.left != null) {
        min = Math.min(min, minElem(node.left));
    }
    if(node.right != null) {
        min = Math.min(min, minElem(node.right));
    }
    return min;
}

Answer 3

Recursive implementation of finding minimum value in a generic binary tree: Here is the BinaryTreeNode class:

package binaryTrees;

public class BinaryTreeNode {

private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
private int max;
private int min;

public int getMax() {
    return BinaryTreeOps.maxValue(this);
}
public int getMin() {
    return BinaryTreeOps.minValue(this);
}

public BinaryTreeNode(){

}
public BinaryTreeNode(int data){
    this.data = data;
}

public int getData() {
    return data;
}
public void setData(int data) {
    this.data = data;
}
public BinaryTreeNode getLeft() {
    return left;
}
public void setLeft(BinaryTreeNode left) {
    this.left = left;
}
public BinaryTreeNode getRight() {
    return right;
}
public void setRight(BinaryTreeNode right) {
    this.right = right;
}
}

Here is the BinaryTreeOps class with the minValue operation: The crux is to use a static variable min so that we reset the same static variable every time we find a value lower than the previous value. It returns zero if pass a null node. You can modify this behaviour as per you requirement.

package binaryTrees;

public class BinaryTreeOps {
private static int min;

public static int minValue(BinaryTreeNode node){
    min=node.getData(); //imp step, since min is static it is init by 0
    minValueHelper(node);
    return min;
}
public static void minValueHelper(BinaryTreeNode node){
    if(node==null)
        return;
    if(node.getData()<min)
        min=node.getData();
    if(node.getLeft()!=null && node.getLeft().getData()<min)
        min=node.getLeft().getData();
    if(node.getRight()!=null && node.getRight().getData()<min)
        min=node.getRight().getData();
    minValueHelper(node.getLeft());
    minValueHelper(node.getRight());
}
}

Answer 4

The problem is that you allow the function to be called on an empty tree. If bt is NULL then you are going to return an uninitialised value for min, which it seems just happens to be 0.

I don't like how you actually search the entire tree. FindMin should be O(logN) (if your tree is balanced), not O(N). I suggest you don't call blindly. Instead, always follow the path that is guaranteed to lead to a minimum. As soon as you find that value, your recursion stops:

int FindMin( struct TreeNode *bt )
{
    if( !bt)
        return 0;  // Only if the tree contains nothing at all
    if( bt->leftChild )
        return FindMin(bt->leftChild);
    return bt->data;
}

It's that easy.

Notice that I don't go down the right branch, because that will always be larger than the current node.