Creating Random Binary Trees

Given a number N, create a random binary tree with the numbers [1..N]. It can actually be done in NLogN time.

1/ Have an index at 2 (assuming root = 1. This can be modified if needed by shuffling the numbers 1..N at a pre-step)

2/ The outer loop will continue until index reaches N, hence O(N)

3/ The inner loop is the most interesting one. It will traverse down the tree randomly trying to go either left or right, placing the current (ref-based) index there

4/ Notice that in #3, the max distance that the inner loop will travel is the height of the tree, which will be on average O(Log(N))

5/ Putting that altogether, you have an NLogN algorithm

6/ Once can also force a "lean left" or "lean right" during the randomness. This will force the tree to be larger towards the left or right. Using a value in the middle (50) ensures uniform distribution

Code is down below. 

I miss my father. He passed away on 5/18/2022 after a long battle in the ICU. Eternally loved.

ACC.

public TreeNode CreateRandomBinaryTree(int n)
{
    TreeNode root = new TreeNode(1);

    int nextIndex = 2;
    Random rdObject = new Random();
    while (nextIndex <= n)
    {
        CreateRandomBinaryTree(root, ref rdObject, 50, ref nextIndex, n);
    }

    return root;
}

private void CreateRandomBinaryTree(TreeNode currentNode,
                                    ref Random rdObject,
                                    int percentageLeanLeft,
                                    ref int nextIndex,
                                    int n)
{
    if (nextIndex > n || currentNode == null) return;

    //Left
    if (rdObject.Next(0, 100) < percentageLeanLeft)
    {
        if (currentNode.left == null && nextIndex <= n)
        {
            currentNode.left = new TreeNode(nextIndex);
            nextIndex++;
        }
        CreateRandomBinaryTree(currentNode.left, ref rdObject, percentageLeanLeft, ref nextIndex, n);
    }

    //Right
    if (rdObject.Next(0, 100) >= percentageLeanLeft)
    {
        if (currentNode.right == null && nextIndex <= n)
        {
            currentNode.right = new TreeNode(nextIndex);
            nextIndex++;
        }
        CreateRandomBinaryTree(currentNode.right, ref rdObject, percentageLeanLeft, ref nextIndex, n);
    }
}