Recursively finding the minimum value in a Binary Tree in Java

Question

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

Welcome to Stack Overflow! We are a question-and-answer site, not a coders-for-hire service. Please explain what you have tried so far and why it hasn't worked. See: Why is "Can someone help me?" not an actual question? — Joe C
– Joe C, Commented Feb 12, 2017 at 21:10
@JoeC Agreed. However, you should vote to close in this situation. — nhouser9
– nhouser9, Commented Feb 12, 2017 at 21:16
@GabrielOshiro Correct, but you should vote to close in that case. — nhouser9
– nhouser9, Commented Feb 12, 2017 at 21:16
@nhouser9 I'd love to, but I don't yet have enough reputation to do so. — Joe C
– Joe C, Commented Feb 12, 2017 at 21:17
@GabrielOshiro thank you for the advice, have I made it better? — Naman Shah
– Naman Shah, Commented Feb 12, 2017 at 21:42

OneCricketeer · Accepted Answer · 2017-02-12 21:48:34Z

2

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;
}

edited Feb 12, 2017 at 21:48

answered Feb 12, 2017 at 21:43

OneCricketeer

193k20 gold badges146 silver badges276 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursively finding the minimum value in a Binary Tree in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related