drawing a binary search tree

[cgen]

Assuming that the values 1 to 7 are equally likely (if chosen randomly):

Draw a 7-node binary search tree containing these values that would, on average, give the fewest number of comparisons.

I'm not exactly sure how to answer this question

[Taywin]

It means that if you randomly pick a number from 1~7, you should get a different binary tree when you do an insertion. For example, if you draw a number from 1~7 and the result of the order is 1, 2, 3, 4, 5, 6, 7, you will get a long tree line when you build a binary tree (using binary tree insertion rules).

/*
   1
  / \
null 2
    / \
  null 3
      / \
    null 4
        / \
      null 5
          / \
        null 6
            / \
          null 7
              / \
           null null
*/

What your goal is to find an extreme case that will create a balanced tree. I gave you one extreme case which results in maximum comparison. You need to look for the other.

[cgen]

Thanks a lot for you reply. I'm not sure but I'm guessing that the extreme case that will create a balance tree will be to take 4 as the root

4
         /       \
        3          5
      /   \      /   \
     2   null   null  6
    /  \             /   \
   1  null          null   7
  /  \                    /  \
null null             null   null

[Taywin]

You are on the right track. Unfortunately, the tree you created is not a balanced tree. You need to apply the insertion rules of binary tree.

/*
  - If the current node is null, assign the inserting value to the node and done.
  - If it is not null, compare the value of the node with the inserting value.
    - If the inserting value is less than the current node value, traverse to the left child
    - Otherwise, traverse to the right child
*/

In your tree, the random order could be "4, 3, 2, 1, 5, 6, 7" and there are 12 comparisons to create the tree. The balanced tree will have only 10 comparisons.