I'm trying to understand what a random binary tree is. According to Wikipedia:

Two different distributions are commonly used: binary trees formed by inserting nodes one at a time according to a random permutation, and binary trees chosen from a uniform discrete distribution...

If I start with a root and then append nodes randomly with no consideration to depth. Would that be considered a random binary tree? Or am I missing something?

enter image description here

  • $\begingroup$ What do you mean by "with a random leaf as parent"? What is logic behind adding a single node? For example, node adding like in a binary search tree. $\endgroup$ – fade2black Jul 14 '17 at 22:55
  • $\begingroup$ I actually just meant randomly appending to the bottom rather than doing any sort of inserts. I shouldn't have said leaf. @fade2black $\endgroup$ – Philip Kirkbride Jul 14 '17 at 22:55

A random binary tree is any tree that is generated by any random process. So, yes. You have described a random process that generates a binary tree; you can describe the result as a random binary tree.

At a technical level, if you have any random variable whose values are binary trees, it would be reasonable to call that a "random binary tree".

Wikipedia is saying that there are two random processes that are particularly commonly considered. But those aren't the only possibilities. You've described a third possibility, and that's also valid.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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