Suppose the datatype for a BST is defined as follows (in SML)

```
datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

```

So there are two cases one in which the BST is `Empty` or it can have a (key,value) as well as two children.

Now, for the case of an AVL where the condition is

> 
> In an AVL tree, the heights of the two child subtrees of any node differ by at most one  
> 
> - [AVL tree Wikipedia](http://en.wikipedia.org/wiki/AVL_tree)
> 
> 
> 

I want to able to create a height function for use to check whether the tree is balanced. My current setup is as follows

```
fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

```

I tried to separate the Tree into three conditions

1. A empty Tree
2. A Tree with a root node
3. A populated tree

The reason for this is that there does not seem to be a canonical source on what the value is for the height of an `Empty` Tree as opposed to one in which only has a root. For the purposes of my balance function it did the job, but I rather try to understand why there isn't a canonical answer for the height of an `Empty` Tree.

There is a canonical answer, in a matter of speaking on [Wikipedia](http://en.wikipedia.org/wiki/Tree_height#Terminology) but while initially doing research on this on Stack Overflow I arrived at many comments stating this to be wrong/incorrect/unconventional

> 
> Conventionally, the value −1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.)
> 
> 
> 

I grabbed the question from which my uncertainty appeared

[What is the definition for the height of a tree?](https://stackoverflow.com/questions/2209777/what-is-the-definition-for-the-height-of-a-tree)

> 
> I think you should take a look at the [Dictionary of Algorithms and Data Structures](http://www.itl.nist.gov/div897/sqg/dads/) at the NIST website. There definition for height says a single node is height 0.
> 
> 
> The [definition of a valid tree](http://www.itl.nist.gov/div897/sqg/dads/HTML/tree.html) 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.
> 
> 
>