8

I'm somewhat confused between the logic of calculating the height of binary tree.

Code 1

public static int findHeight(Tree node) {
    if(node == null)
        return 0;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}

Code 2

public static int findHeight(Tree node) {
    if(node == null)
        return -1;
    else {
        return 1+Math.max(findHeight(node.left), findHeight(node.right));
    }

}

I think, the second one is correct, since it gives the correct answer for below code :-

Tree t4 = new Tree(4);
Tree t2 = new Tree(2);
Tree t1 = new Tree(1);
Tree t3 = new Tree(3);
Tree t5 = new Tree(5);

t4.left = t2;
t4.right = t5;

t2.left = t1;
t2.right = t3;

// Prints "Height : 2" for Code 2
// Prints "Height : 3" for Code 1
System.out.println("Height : " + findHeight(t4));

I'm confused because many of other SO answers shows the logic for calculating height as per Code 1

Contradictory logics

UPDATE:

All, I've a basic doubt as to what is exactly the height of tree ?

1. Is it the no of nodes between the root and deepest node of tree ( including both - the root & deepest node ) ?

2. Is it the no of edges between the root and deepest node of tree ?

OR

3. Is it just the matter of implementation of every individual - Both approaches are correct ?

Community
  • 1
  • 1
tmgr
  • 1,187
  • 3
  • 14
  • 16

3 Answers3

7

The difference all lies in if an empty tree has height -1 or 0.

According to Wikipedia:

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).

and

The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.

So you might be right - the second one agrees about this.

Of course, these are all definitions - I would not be too amazed to see a definition that agrees with the first version.

zw324
  • 26,764
  • 16
  • 85
  • 118
  • The length of a path is the count of edges, so I'd say 2. – zw324 Jul 03 '13 at 14:03
  • But, as per code 1, which many SO users says (including Jon Skeet) http://stackoverflow.com/q/5763854/2546848 , that would result in incorrect answer for my above code .. Isn't it ? – tmgr Jul 03 '13 at 14:05
  • These kind of definitions can vary a lot - even books as CLRS and Knuth sometimes have different definitions. Also, Jon can be (rarely) inaccurate too - this is a definition most people probably have forgot (I definitely did). – zw324 Jul 03 '13 at 14:07
  • Are both approaches correct at their usage ? Depends on scenario ? – tmgr Jul 03 '13 at 14:08
  • Don't mix them you should be most of the time good - some formula could get uglier with one definition, of course. For example, the max number of nodes is 2 ^ n - 1 by the Wiki definition, 2 ^ (n - 1) - 1 by the other version. – zw324 Jul 03 '13 at 14:09
0

Your example is of height 3 (t4 is a root, t4.left is t2, t2.left is t1) if your understanding of height is (1 root node is of height 1, root node with a child or two is of height 2, etc)

t4.left = t2;
t4.right = t5;

t2.left = t1;
t2.right = t3;

So code 1 is right :))

Tala
  • 8,888
  • 5
  • 34
  • 38
  • The second one is true, but for many situations developers go with the first one when implementing the height. So the answer is 3 :)) – Tala Jul 03 '13 at 14:04
0

Code 0 will count the root as height 1 (root should be 0). Which means all subsequent trees will be one too many

Kevin
  • 1,626
  • 16
  • 30