CODEWITHSUNDEEP
javarecursionbinary-search-tree
move_slow_break_things
move_slow_break_things

Reputation: 847

Checking to see if a binary search tree is degenerate

I want to check if a binary search tree is degenerate or not (Is it a linked list or indeed a tree?) I've been trying for a while and have come up with nothing that works. I did come up with a nonrecursive solution which I thought was quite clever but the specifications state it has to be a recursive solution and I'm having translating it from non-recursive to recursive.

Here's my non-recursive solution (well not really because size and height are both implemented recursively. This method however is not).

public boolean isDegenerate(){
        if(this.size() == this.getHeight()){
            return true;
        }
        return false;
    }

Upvotes: 1

Views: 3901

Answers (1)

Jiri Tousek
Jiri Tousek

Reputation: 12450

Well, if you want a "more recursive" solution, how about this?

public boolean isDegenerate() {
    if (this.left != null) {
        if (this.right != null) {
            return false; // not degenerate, has two children
        } else {
            return this.left.isDegenerate();
        }
    } else {
        if (this.right != null) {
            return this.right.isDegenerate();
        } else {
            return true; // we arrived at the bottom without seeing any node with two children
        }
    }
}

Upvotes: 5

Related Questions