DSA When BSTs Go Bad
A binary search tree degenerates when sorted values are inserted one after another. Each new value becomes the deepest node, and the tree turns into a linked list.
Sorted inserts make a chain
Five rising values each turn right at every node. The height reaches four edges for five nodes, and the left child of the root stays empty.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def insert(root, value):
visits = 0
if root is None:
return TreeNode(value), 0
node = root
while True:
visits += 1
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
return root, visits
node = node.left
else:
if node.right is None:
node.right = TreeNode(value)
return root, visits
node = node.right
def height(root):
if root is None:
return -1
return 1 + max(height(root.left), height(root.right))
def build(values):
root = None
total = 0
for v in values:
root, visits = insert(root, v)
total += visits
return root, total
root, total = build([10, 20, 30, 40, 50])
print("height in edges:", height(root))
print("insert visits total:", total)
node = root
chain = []
while node is not None:
chain.append(node.value)
node = node.right
print("right chain:", chain)
print("left child of root:", root.left)A shuffled order branches
A fixed-seed shuffle of the values 1 to 15 branches both ways. The height lands at six edges for fifteen nodes.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def insert(root, value):
visits = 0
if root is None:
return TreeNode(value), 0
node = root
while True:
visits += 1
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
return root, visits
node = node.left
else:
if node.right is None:
node.right = TreeNode(value)
return root, visits
node = node.right
def height(root):
if root is None:
return -1
return 1 + max(height(root.left), height(root.right))
def build(values):
root = None
total = 0
for v in values:
root, visits = insert(root, v)
total += visits
return root, total
import random
values = list(range(1, 16))
random.Random(42).shuffle(values)
print("insert order:", values)
root, total = build(values)
print("height in edges:", height(root))
print("insert visits total:", total)Search pays for the skew
Searching for 15 walks the whole chain in the sorted-built tree. The same search takes three visits in the shuffled-built tree, and the insert totals show the same gap.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def insert(root, value):
visits = 0
if root is None:
return TreeNode(value), 0
node = root
while True:
visits += 1
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
return root, visits
node = node.left
else:
if node.right is None:
node.right = TreeNode(value)
return root, visits
node = node.right
def height(root):
if root is None:
return -1
return 1 + max(height(root.left), height(root.right))
def build(values):
root = None
total = 0
for v in values:
root, visits = insert(root, v)
total += visits
return root, total
import random
sorted_root, sorted_total = build(list(range(1, 16)))
values = list(range(1, 16))
random.Random(42).shuffle(values)
mixed_root, mixed_total = build(values)
def search(root, target):
visits = 0
node = root
while node is not None:
visits += 1
if node.value == target:
return visits
node = node.left if target < node.value else node.right
return visits
print("search 15 in sorted-built tree visits:", search(sorted_root, 15))
print("search 15 in shuffled-built tree visits:", search(mixed_root, 15))
print("insert totals:", sorted_total, "vs", mixed_total)Example
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def insert(root, value):
visits = 0
if root is None:
return TreeNode(value), 0
node = root
while True:
visits += 1
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
return root, visits
node = node.left
else:
if node.right is None:
node.right = TreeNode(value)
return root, visits
node = node.right
def height(root):
if root is None:
return -1
return 1 + max(height(root.left), height(root.right))
def build(values):
root = None
total = 0
for v in values:
root, visits = insert(root, v)
total += visits
return root, total
import random
print("n | sorted height | sorted visits | shuffled height | shuffled visits")
for n in (10, 20, 40, 80):
sorted_root, sorted_total = build(list(range(1, n + 1)))
values = list(range(1, n + 1))
random.Random(1000 + n).shuffle(values)
mixed_root, mixed_total = build(values)
print(n, "|", height(sorted_root), "|", sorted_total, "|",
height(mixed_root), "|", mixed_total)Key points
- A BST insert walks down one path, going left for smaller values and right for larger ones
- Sorted inserts always turn right, so no left child is ever created
- Height here means the longest root to leaf path, counted in edges
- Insert visits in a skewed tree grow like 1 plus 2 plus up to n, a quadratic total
- A shuffled insert order keeps the height far below n on the same values
In this example, sorted inserts and fixed-seed shuffled inserts build trees of 10, 20, 40 and 80 nodes. The sorted height always equals n minus 1, and its visit total reaches 3160 at n equals 80. The shuffled heights stay between 4 and 14 across the same sizes. Skew, not size, is what makes the operations expensive.
Note
the shuffle here uses a fixed seed, so the printed heights repeat on every run.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Inserting 1, 2, 3 up to 100 into an empty BST gives a tree of what height in edges?