'Why does order of inserts to binary tree matter?

I know that the order does matter when inserting elements into a binary search tree and that elements inserted in different order will lead to different binary tree structures, but I'm not sure how to explain WHY in a coherent way.

insertbinary-treeelementsoperator-precedence


Solution 1:[1]

If the insertions are done in an numerical order for a group of numbers, a binary tree becomes a linked list which affects the search performance (it becomes O(n)). The reason being tree is heavily unbalanced.

Solution 2:[2]

Another simple explenation

The first node you add to the BST (binary search tree) will always be the root and cannot be changed after initialization. This fact alone can explain pretty obviously why the ordering matters. Given N elements, you have already N possible (and more importantly, different) BST structures.

Simple Example

nums = [1,5,10]

/*

TREE1
1 (root)
 \
  5
   \
   10


TREE2
   5 (root)
  / \
 1  10

TREE3
    10 (root)
   /
  5
 /
1

*/

? key takeaway

  • ordering will affect the balance of a tree (TREE2 is balanced, TREE1 and TREE2 are not)
  • balancing affects efficiency for BST operations, e.g. traversal/search:
    • perfectly balanced O(log_n) time
    • unbalanced: O(n) time (= worst case).

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Prasad Y
Solution 2 dcts

Related Questions