Lets take a
Binary Tree with
n nodes (and
n-1 edges). If
h is the height of the tree, then
n] depending if the tree is balanced or not. The minimum height is reached if the tree is "completed", i.e. the nodes either have two children or are leaves. The maximum height is reached when every node bar one have one child only.
There is obviously a correlation between the number of children of the nodes and the height of the tree. I would like to know more about how informations regarding the number of children by node can refine the set of possible values for
h. A few (easy) examples follows, but does it exist a general formula for putting boundaries for the possible values of
Such a formula would be extremly useful for calculating the computational complexity of operations upon Binary Trees. For example it is known that in a common Binary Search Tree if the node u has two children then both its predecessor and successor have only one child. This fact could be used to narrow the possible values for
h and compare with the operations of others Binary Search Tree, like the AVL Trees or the Red-Black Trees.
The deep of a node u, indicated by d(u), is the distance between u and the root. d(root) = 0 by definition.
The height of a node u, indicated by h(u), is the distance between u and its most distant descendant. h(root) =
h by definition.
Let define c0 the number of nodes with zero children (i.e. leaves), c1 the number of nodes with one child, c2 the number of nodes with two children. Because of the definition of the Tree, we know that
n = c0 + c1 + c2.
If c2 = 1 and c1 =
n-2]: the minimum value is reached if the node with two children is the root, the maximum value is reached if the node with two children is the one with deep equals to 1.
If c2 = 3 and c1 =
n-4]: the minimum value is reached if the nodes with two children are the root and its children, the maximum value is reached if the nodes with two children are those with the least deep.
If c2 =
n/2 and c1 = 0 (or 1 if
n is odd), then the tree is complete and
h can only be log2(
If c2 = 0 and c1 =
n-1, then the tree is completely unbalanced and
h can only be