# How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $$\frac{1}{2}$$ probability of choosing right or left. I know that the following property holds for height $$h$$, but it's difficult to add the probability:$$h_{tree}= 1+max(h_{left}, h_{right})$$I think that this version/random tree differs from the random (search) tree mentioned in CLRS chapter 12.4, where you pick a random element from a sorted list $$\{1,\dots, n\}$$ and insert based on whether the visited node is greater or less than the inserted element. Because, here we choose each path on each visited node to be random.

Note: the binary tree has all its elements at the leafs and internal nodes are only used for routing (see Figure 1.)

//pseudocode
insert(i, tree):
if at leaf v:
split(); //Create a parent u and set its children to be the leaf v and element i.
else:
int left = random()
int right = random()
if (left > right):
insert(i, left-subtree):
else:
insert(i, right-subtree)


Figure 1:

• does split create a parent with two children (split removes two leaves and adds two new ones)? Or does it create a parent with just one child? Mar 13 '21 at 17:59
• split is only used when the inserted element ends at a leaf. So, a parent node with two children is created. The first child is the old leaf, and the second child is the newly inserted element. Mar 13 '21 at 18:12
• Are you looking for a lower and upper bound or exact values? Mar 13 '21 at 18:45
• The expected height. Due to the probability there is no exact value. Mar 13 '21 at 18:52
• The expected value is a well defined exact value. This seems to be what you are searching for: en.wikipedia.org/wiki/Random_binary_tree#Random_split_trees If you look at your version and pretend that the leaves are just placeholders, the wikipedia version and yours are the same. $O(\log n)$ is the expected height. If you look into the article you can find even better approximations. Mar 13 '21 at 19:02