CODEWITHSUNDEEP
javarecursiontree
Naman Shah
Naman Shah

Reputation: 45

Recursively finding the minimum value in a Binary Tree in Java

I need to find the minimum value in a tree of Strings that is NOT a Binary Search Tree recursively. I tried looking at some other questions like mine, but I couldn't figure out the answer.

I've figured out that I have to find the min of each of the subtrees, then compare it to the root, and return the minimum value. But I'm not sure how to actually write that.

This is the header:

public static Object min(TreeNode t){

}

EDIT: So what I've figured out so far is this

public static Object min(TreeNode t){
    if(t == null){
        return ______;
    }
    else if(min(t.getLeft().compareTo(min(t.getRight()) < 0){
        if(min(t.getLeft()).compareTo(t) < 0){
            return min(t.getLeft());
        }
    }
    else if(min(t.getLeft().compareTo(min(t.getRight()) > 0){
        if(min(t.getRight()).compareTo(t) < 0){
            return min(t.geRight());
        }
    }
    else{
        return t;
    }
}

I think I'm going in the right direction, but I'm not sure what fits in return statement in the null base case. Could someone help me understand what should go in the return statement and why? And if I'm doing this right? Thanks

Upvotes: 2

Views: 2741

Answers (1)

OneCricketeer
OneCricketeer

Reputation: 191728

You need to handle getLeft or getRight also being null, otherwise your code ends up exceptions.

Then, your case for any greater than comparison should not be entered if you want "the minimum", I don't think.

Who said you couldn't return null? 

public static Object min(TreeNode t){
    TreeNode min = t;
    if(t == null){
        return min;
    }
    final TreeNode left = t.getLeft();
    final TreeNode right = t.getRight();

    if (left == null && right == null) 
        return min;

    if(left != null && left.compareTo(t) <= 0) {
        min = (TreeNode) min(left);
    if(min != null && right != null && right.compareTo(t) > 0){ // not sure about this 
        min = (TreeNode) min(right);
    }
    return min;
}

Upvotes: 2

Related Questions