Grow a tree one value at a time
Build a search tree by inserting values in the order they arrive, and see how the order of insertion shapes the tree and its height. About 14 minutes.
Each value finds its place
To insert a value, start at the root. If the value is smaller than the current node, go left. Otherwise go right. When the place you want to go to is empty, put a new node there. The new node is always a leaf.
The first value has no tree to enter, so it becomes the root. Building a tree from a list is just inserting its values one by one.
tail = root
while tail.right:
tail = tail.right
tail.right = TreeNode(v)- inserted
- 7
7 arrives first and becomes the root.
Order decides the shape
The same set of values can make many different trees. Insert 1, 2, 3, 4 in that order and each value goes right of the last, making a chain of height 4. Insert 2, 1, 3, 4 and the tree is shorter.
The height of the tree is the number of levels, so it is the longest walk down. It is the cost of one search in the worst case.
# 1, 2, 3, 4 -> a chain of height 4 # 2, 1, 3, 4 -> height 3
The values 1, 2, 3, 4, 5 are inserted in this order. What is the height of the tree?
- A5, a chain going right
- B3, a balanced tree
- C2
Show the answer
5, a chain going right. Each new value is larger than all before it, so it goes right.
Build a search tree by insertion
Given an array values, build a binary search tree by inserting the values one by one in the given order into an initially empty tree. A value smaller than a node goes into its left subtree, and a value equal or larger goes into its right subtree. Return the root.
values = [5, 3, 6, 2, 4] → [5, 3, 6, 2, 4]
0 ≤ length of values ≤ 5,000 · -100,000 ≤ values[i] ≤ 100,000