Height of a tree with only one node

tree height binary-tree discrete-mathematics
Snowman picture Snowman · Oct 31, 2010 · Viewed 27.5k times · Source

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)?

Answer

Jack picture Jack · Oct 31, 2010

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.

Related questions

How to implement a tree data-structure in Java?

Is there any standard Java library class to represent a tree in Java? Specifically I need to represent the following: The sub-tree at any node can have an arbitrary number of children Each node (after the root) and it's children …

Read More
How can I implement a tree in Python?

I am trying to construct a General tree. Are there any built-in data structures in Python to implement it?

Read More
Unable to show a Git tree in terminal

Killswitchcollective.com's old article, 30 June 2009, has the following inputs and outputs git co master git merge [your_branch] git push upstream A-B-C-D-E A-B-C-D-E-F-G \ ----> \ your branch C-D-E G I am interested how you get the tree like-view of commits …

Read More