What is the definition for the height of a tree?

Question

I can't seem to find a definitive answer for this, I'm trying to do some elementary proofs on heaps but here's what's throwing me off a little bit:

Is an empty tree valid? If so, what is its height?
I would think this would be 0.

What is the height of a tree with a single node?
I would think this would be 1 but I have seen definitions where it is 0 (and if this is the case then I don't know how to account for an empty tree).

Solution 1

I think you should take a look at the Dictionary of Algorithms and Data Structures at the NIST website. There definition for height says a single node is height 0.

The definition of a valid tree does include an empty structure. The site doesn't mention the height of such a tree, but based on the definition of the height, it should also be 0.

Solution 2

Height of a tree is the length of the path from root of that tree to its farthest node (i.e. leaf node farthest from the root).

A tree with only root node has height 0 and a tree with zero nodes would be considered as empty. An empty tree has height of -1. Please check this.

I hope this helps.

Solution 3

I have seen it used in both ways (counting a single node as 0 or 1), but the majority of sources would define a root-only tree as a tree of height 0, and would not consider a 0-node tree valid.

Solution 4

If your tree is a recursively defined data structure which may be either empty or a node with a left and right subtree (for example search trees, or your heap), then the natural definition is to assign 0 to the empty tree and 1 + the height of the highest subtree to a nonempty tree.

If your tree is a graph then the natural definition is the longest path from the root to a leaf, so a root-only tree has depth 0. You normally wouldn't even consider empty trees in this case.

Solution 5

The height of a tree is the length of the longest path to a terminal node in either of its children.

Wikipedia says the height of an empty tree is -1. I disagree. An empty tree is literally just a tree containing one terminal node (a null or special value which represents an empty tree). Since the node has no children, the length of its longest path must be the empty sum = 0, not -1.

Likewise, a non-empty tree has two children, so by definition there is at least a path >= 1 to a terminal node.

We might define our tree as follows:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec height = function
    | Node(left, x, right) -> 1 + max (height left) (height right)
    | Nil -> 0

View more solutions

Comments

[Brad]

Thanks, it's nice to have a reliable source to cite for this (don't think a professor or peer review would consider Wikipedia an acceptable source). Their definitions seem to be a bit contradictory though, they define a tree as either "empty (no nodes), or a root and zero or more subtrees". But their definition of height is defined in terms of the root node.

[nlucaroni]

I agree. I think you should definitly email him (so you can get cited on that page for bringing up this distinction). But considering the definition implies the maximum number of edges from the root to a leaf, we have to say that an empty tree has height 0.

[nlucaroni]

I just checked the new Cormen and he doesn't make the distinction (p. 1177) either.

[Keyur Padalia]

I would say that the height of an empty tree is either -1, or -infinity. Definitely not 0.

[Keyur Padalia]

"An empty tree is literally just a tree containing one terminal node." Nope, even emptier than that...

[Brad]

I think, lacking an authoritative source to cite, I'm going to say that an empty tree has an undefined height. This way the number of nodes in a complete binary tree of height h is between 2^h and 2^(h+1)-1. And if you flip it around to solve for h based on n you end up taking log2(0)=undefined when the tree is empty. It makes for a tidy definition and pretty proof at least.

[Arnkrishn]

I believe its a matter of convention used in implementation. As all positive height values and the height value zero would get represented when you have one or more nodes in the tree, you ought to have something to represent an empty tree. So the convention has it as -1. You can have it as any other negative value. Its a matter of implementation as the actual abstraction of the data structure - tree would not cover these things.

[yfeldblum]

The height of an empty tree is not defined. The height of a tree is the height of the root note of that tree (which is one plus the maximum of the heights of its children, or zero if it has no children). An empty tree does not have a root node, and so cannot be said to have a height.

[hencrice]

Actually the new definition says that the height of an empty tree is not defined.

[Admin]

The convention of the empty tree having height -1 actually has some practical use in AVL trees in that it simplifies calculating the balance factor and when to rotate children. This implementation shows it in practice: users.cis.fiu.edu/~weiss/dsaajava/code/DataStructures/…

[John Clements]

I'd like to point out that (a) you're obviously right, and (b) the NIST and many other people don't see things (y)our way. I believe this unfortunate state of affairs is principally due to CLR, which suffers from "fear of null".

[John Clements]

FWIW, CLR appears to suffer from "fear of null" here. Knuth suggests (though the reference is in passing) that the empty tree should have a height of zero. The decision on the part of the NIST to follow the lead of CLR is unfortunate; it needlessly complicates code that wants to use the notion of height.