Height of tree with single node

Question

I have googled it that there is no right answer for tree height having only one node . Sometimes it node count and sometimes it is edges count causes sometimes it is 1 and other time it is 0 . what are the cases when node count is used and other time edge count is used ?

Answer 1

It depends entirely on your definition of (1) tree, and (2) height. But we certainly wish to maintain the property that height is a total function from trees to inteters; there should be no tree of undefined height.

Suppose for example we have this definition of a binary tree:

A tree is defined as either (1) the empty tree, or (2) a pair of trees, called the left and right subtrees.

type t = Empty | Node of t * t

Now we can define height, which should be a total function: the height of an empty tree is zero -- what else could it be? -- and the height of a non-empty tree is the larger of the heights of the sub-trees plus one:

let max x y = if x > y then x else y
let rec height tree = match tree with 
  | Empty -> 0
  | Node (left, right) -> 1 + max (height left) (height right)

Now, notice the chain of logic that got us here:

• height is a total function
• empty is a legal tree
• therefore an empty tree must have a height
• the only sensible height for an empty tree is zero
• therefore the height of a tree with a single node must be one.

If we deny some of those premises then we can come up with other answers. For example, what if there were no empty trees?

A tree is defined as a list, possibly empty, of trees:

type t = Node of t list

And again we could come up with a definition of height: the height of a node with an empty list is defined as zero, and the height of a node with non-empty children is the largest child height plus one.

let max x y = if x > y then x else y
let rec height tree = match tree with
  | Node [] -> 0
  | Node h :: t -> max (1 + height h) (height (Node t)) 

In this definition the height of a tree with a single node is zero, and we are counting edges. Again, look at our reasoning:

• height is a total function
• an empty tree is not a legal tree, but a leaf is
• therefore a leaf must have a height
• a sensible height for a leaf is zero
• therefore a tree that is a single leaf could have height zero.

But we could also have said that the height of a leaf is one, with the same definition otherwise, and we'd be counting nodes. There's no objection to that logically.

what are the cases when node count is used and other time edge count is used ?

If an empty tree is legal then plainly only the node count makes sense. If we try to count edges then there is no way to distinguish the height of the empty tree from the height of a single-node tree, and keep height a total function.

If an empty tree is not legal then either makes sense. Since the relationship between the two height functions is "they differ by exactly one", it doesn't matter which definition you use; if you want to use the other definition, just add or subtract one appropriately.

When balancing a tree we don't care about the absolute heights; we care about the differences in heights between two trees. In those algorithms whether we count edges or nodes is irrelevant. The differences will be the same regardless. A lot of the time it doesn't matter, so pick whichever you like better.

Answer 2

The height of a node is the number of edges on the longest path from the node to a leaf.A leaf node will have a height of 0. Height of tree is height of its root node. In your case height of tree will be 0. for detailed answer check this one out. What is the difference between tree depth and height?