Random binary tree

57 Views Asked by At

I'm considering a binary tree $T$. Similar to a binary search tree, it inserts a new node from root to bottom. we flip a coin to decide the new node going left or right in each level.

A property in this tree $T$ may be:

For each node $v \in T$, the number of nodes in its left and right should be similar.

Now I am curious about the property and boundary of its height, shortest path, longest path. I find some papers about random binary search trees, however, combined with permutations of $\{1,2,...,n\}$, they are different with $T$. Is there any paper for the tree $T$ in this question? I have tried to find but no result concerning.

URL for random binary search trees: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152.1289&rep=rep1&type=pdf