1
$\begingroup$

I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1. With that in mind, what would be the number of binary search trees (don't have to be balanced) that have the maximum possible height for n-nodes?

So far, I know that the maximum height of any binary search tree of n-nodes is n-1 since we're counting edges. So for example, a binary search tree of 3 nodes has a maximum height of h = 3-1 = 2 and there are 4 possible trees with n-nodes that have the maximum height of 2.

I also know that for n-nodes, there are (2n)!/((n+1)!n!) possible trees.

I'm able to find this manually for trees where n is small but would like to find a formula for any n.

EDIT:
The BST definition I am working with defines a Binary Search tree as a binary tree where each node has at most 2 children and does NOT need to be nearly-complete, so you could have a tree of 3 nodes with a height of 2. It also satisfies the BST property where all nodes in the left subtree of a node x has keys smaller than x's key and all nodes in the right subtree of a node x has keys larger than x's key.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Have you plugged in the values you've found for small $n$ in the Online Encyclopedia of Integer Sequences? $\endgroup$
    – Yuval Filmus
    Feb 17, 2018 at 9:32
  • $\begingroup$ In a binary search tree, every internal node has two children. In particular there is no binary search tree with only two nodes. A binary search tree with three nodes has height 1, and in general the maximum height of a binary search tree with $n$ nodes is $n-2$. There are $2^{n-3}$ binary trees of this height, since at every internal node but the last one we choose which side is a leaf. $\endgroup$
    – Yuval Filmus
    Feb 17, 2018 at 14:17
  • $\begingroup$ @YuvalFilmus The definition I'm working with considers a binary search tree to be a binary tree with at most 2 children, but it does not need to be nearly-complete. It also has the BST property. So I can have a 3-node tree of height 2. $\endgroup$
    – Paradox
    Feb 19, 2018 at 21:35

1 Answer 1

Reset to default
2
$\begingroup$

The number of trees with $n$ nodes of height $n-1$ is $2^{n-1}$. Indeed, every internal node has exactly one child, which can either be the left child or the right child. Since there are $n-1$ internal nodes, this gives $2^{n-1}$ options.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.