balanced() binary tree

Question

I need to write a method that determines whether a binary tree is balanced. So first I'm going to have to determine the height of each side of the tree. But I'm having trouble understanding how I am going to count the max length of a subtree, without counting all the nodes in the subtree. This question is very difficult to ask for me, so you guys can understand.

// primary method
public int Height()
{
    int h = height( root );
}

// recursive method
private int height( Node x )
{
    if( x == null ) return 0;
    count++;                   
    height( x.left );
    height( x.right );
    return count;           
}

Here is my code for calculating the max height of the tree. But i dont know how to determine just the left or right sides' height, and this method seems to count the amount of nodes in the tree itself.

yes i know. but thats why i did'nt ask for the hole balanced tree, just the height and the concept f how to start with the balnced tree. why does my code come out so studip? — Ruben Van St Aden, Apr 30 '11 at 17:39
See http://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced — Dan D., Apr 30 '11 at 17:41

score 1 · Answer 1 · answered Apr 30 '11 at 17:41

This method will not even compile, because of the return; statement - you need to return an int.

So, if(x == null), what should you return? What is the height of an empty tree?

Once you have that figured out, imagine your root has only a left-subtree (root.right == null), and you know the height of the left-subtree. What should the height of the overall tree be?

What if it has only a right subtree?

Now, what if it has both?

Note that you don't need a global counting variable for any of this.

ok beginners mistake with the first return value. if changed my code there. — Ruben Van St Aden, Apr 30 '11 at 17:52

score 1 · Answer 2 · answered Apr 30 '11 at 17:42

1

The height is 1 + max(left.height(), right.height()).

You should return a value instead of setting a variable (count, in your case), otherwise you'll go mad.

answered Apr 30 '11 at 17:42

akappa

10,220
3
39
56

but what i dont understand is that left.height() and right.height() will just return 0. how can they return a value if a dont count for one? – Ruben Van St Aden Apr 30 '11 at 17:54
but what i dont understand is that left.height() and right.height() will just return 0. how can they return a value if a dont count for one? – Ruben Van St Aden Apr 30 '11 at 17:54
cuase i say return 0 when a reach a leaf – Ruben Van St Aden Apr 30 '11 at 17:54
Absolutely right about the variable. Global variables and recursion inevitably lead to madness. – Tom Anderson Apr 30 '11 at 17:55
I think you've problems understanding recursion... try to emulate the recursive call on the root node, starting from the bottom of the tree. – akappa Apr 30 '11 at 17:56
so what your actual compairing to find the max height, is which method( height.left of height.right ) was called the most? – Ruben Van St Aden Apr 30 '11 at 18:11

score 0 · Answer 3 · answered Apr 30 '11 at 17:42

0

The height of a node is one more than the height of its tallest sub-node (hint: use Math.max).

answered Apr 30 '11 at 17:42

sjr

9,769
1
25
36

score 0 · Answer 4 · answered Apr 30 '11 at 20:53

0

Adding to the hints I'll also point out that you really want to use recursion.

answered Apr 30 '11 at 20:53

Shai Deshe

153
1
8

balanced() binary tree

4 Answers4