arrayssortingbinary-search-tree

special property of the root of a BST - middle value?


Is the root node of a BST always guaranteed to be the "middle" value of the BST if all the values of the BST were placed in a sorted array?

Assuming that the first element in an array will be by default the root, and all other elements in the array will then be placed in the BST according to the BST ordering structure (lesser nodes on the left and greater nodes on the right).

If it is not always the "middle value" in what cases is it middle value?


Solution

  • A BST has no guarantee about what its root value is. For example, if you insert the values in ascending order, the root will be the minimum value. If you insert the values in descending order, the root will be the maximum value.

    If you choose an AVL tree as BST, so that it is self-balancing, then you can limit the possibilities for what the root value could have as value, but still it is not guaranteed it would be the middle value. For instance, if you insert the values 3, 2, 7, 1, 5, 8, 4, 6, 9 in that order, then even an AVL tree will not apply any rebalancing actions, and so the value 3 will stay at the root, while the middle value 5 sits at the third level of the tree:

            3
           / \
          2   7
         /   / \
        1   5   8  
           / \   \
          4   6   9