Geek Answers Handbook

Are my recursion conditions correct for calculating the height of a binary tree?

I am trying to find out if my code is right or wrong with your help, because, unfortunately, I can not run it to check.

There are no compilation errors. What I'm trying to do is find the height of a binary tree . Of course, the tree does not have to be balanced.

Each node in a binary tree can have two nodes as children

public int height(RBNode t) { if (t == null) return 0; int heightLeft = height(t.left); int heightRight = height(t.right); if (heightLeft > heightRight) { return heightLeft + 1; } else { return (heightRight + 1); } }

Do you think the recursion conditions are correct? My friend claims that he will always return 0.

0
java recursion
source share
4 answers

Really compact version:

 public int height(RBNode t) { if (t == null) { return 0; } return Math.max(height(t.left), height(t.right)) + 1; }
+5
source share

It looks good, although I would personally change the last bit:

 return Math.max(heightLeft, heightRight) + 1;

I am worried that you cannot run it, though ... why can't you write unit tests around this? I would be nervous from any code that I cannot verify :)

+5
source share

At first glance, while you are walking through the head of a tree, it will return the correct value. But it would be easy to build a test to verify this ...

0
source share

In the code in the question, we don’t get a height of +1? height is defined as 'the length of the path from the root to the deepest node in the tree. A tree with a root (with root) with one node (root) has a depth of zero.' (Wikipedia)

if in the interrogation code, if you give the root to the tree with only 1 node, it will give a height as 1, which should be 0 ..

Please correct me if I'm wrong somewhere.

0
source share

More articles:


All Articles