35

According to Wikipedia,

The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero (or one).

I dont get it - is it zero or one (or both)?

Snowman
  • 31,411
  • 46
  • 180
  • 303
  • Best answer can be found at the following link: http://stackoverflow.com/questions/2597637/finding-height-in-binary-search-tree – akshitmahajan Jan 26 '16 at 19:31

6 Answers6

44

It just an assuption you make for the recursive description of the height of a binary tree. You can consider a tree composed by just a node either with 0 height or with 1 height.

If you really want to think about it somehow you can think that

  • it's 0 if you consider the height as a edge count (so that a single node doesn't have any edge, hence 0)
  • it's 1 if you consider the height as a node count (so that a single node counts as 1)

This is just to describe how much height the smallest tree has, then in any case whenever you add a descending node you will add also a related edge so it will increase accordingly.

In the example provided in wikipedia:

alt text

This tree can have height 4 (nodes) or 3 (edges). It depends if you are counting it by edges or by nodes.

Jack
  • 131,802
  • 30
  • 241
  • 343
  • Oh ok I see. So theres no separate terms to refer to height of nodes and height of edges individually? – Snowman Oct 31 '10 at 22:32
  • 2
    No, there isn't.. the height of a tree is measured as the path length from the root to the deepest node. A path is composed by edges and nodes, and specifically if the path has _n_ edges then it has _n+1_ nodes (this should be quite trivial), that's why you can have to different base cases: a path composed by just a node has 0 edges but 1 node. – Jack Oct 31 '10 at 22:36
14

One advantage of using a node count rather than an edge count is that it distinguishes the empty case (zero nodes, and node level) from the minimal case (one node, and a node level of one). In some cases, an empty tree will not be meaningful, but in other cases an empty try will be perfectly legitimate.

supercat
  • 77,689
  • 9
  • 166
  • 211
9

Depends on convention. There isn't a "right" answer here. I was taught it's 1. But zero is just as correct.

Oren A
  • 5,870
  • 6
  • 43
  • 64
3

I my opinion, Height of one root node should be 0. It makes practical sense as 2^height is also providing you with the number of nodes at that level.

Ritesh
  • 1,809
  • 1
  • 14
  • 16
  • 3
    One could argue the opposite, though. If height is defined inclusively, (2^height)-1 is the maximum size of tree for a given height. – supercat Dec 11 '14 at 15:42
1

Assuming you are calculating the height in a recursive manner in the node class I would do this to return the height without including height of the root (java code):

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

if you want to include the height of the root, then I would do this:

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}
user4617883
  • 1,277
  • 1
  • 11
  • 21
0

depends how you want to interpret the height of a tree. in some applications, a tree with one node is interpreted as having height of one and others consider it as having height of zero.

zerodin
  • 857
  • 5
  • 9