DSA Searching and Inserting in a BST
A BST search walks one path from the root, choosing left or right by comparing the target with each node. Inserting a value places it at the empty slot where that search path runs out.
A search that hits
The search for 6 compares against 8, then 3, then 6 itself. Each comparison sends the walk down one level.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def search_path(root, target):
path = []
node = root
while node is not None:
path.append(node.value)
if target == node.value:
return path, True
if target < node.value:
node = node.left
else:
node = node.right
return path, False
tree = TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6)),
TreeNode(10, None, TreeNode(14)))
path, found = search_path(tree, 6)
print("Path:", path)
print("Found:", found)
print("Comparisons:", len(path))A search that misses
The search for 13 follows the same kind of path and runs out of nodes at 14. The empty left slot of 14 is exactly where 13 belongs.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def search_path(root, target):
path = []
node = root
while node is not None:
path.append(node.value)
if target == node.value:
return path, True
if target < node.value:
node = node.left
else:
node = node.right
return path, False
tree = TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6)),
TreeNode(10, None, TreeNode(14)))
path, found = search_path(tree, 13)
print("Path:", path)
print("Found:", found)
print("Comparisons:", len(path))Insert fills the empty slot
Insert runs the same walk and hangs the new value on the empty slot it finds. The inorder walk afterwards still reads sorted.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(node, order):
if node is None:
return
inorder(node.left, order)
order.append(node.value)
inorder(node.right, order)
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
tree = TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6)),
TreeNode(10, None, TreeNode(14)))
tree = insert(tree, 13)
order = []
inorder(tree, order)
print("Inorder after insert:", order)Example
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
from collections import deque
def levels(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
row = []
for _ in range(len(queue)):
node = queue.popleft()
row.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(row)
return result
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def search_path(root, target):
path = []
node = root
while node is not None:
path.append(node.value)
if target == node.value:
return path, True
if target < node.value:
node = node.left
else:
node = node.right
return path, False
tree = None
for value in [8, 3, 10, 1, 6, 14, 4, 7]:
tree = insert(tree, value)
print("Built by insertions:", levels(tree))
path, found = search_path(tree, 7)
print("Search 7: found", found, "path", path, "comparisons", len(path))
path, found = search_path(tree, 13)
print("Search 13: found", found, "path", path, "comparisons", len(path))Key points
- Each comparison discards one whole subtree from the search
- A search ends at a match or at an empty slot
- The new node always lands as a leaf, at the end of its search path
- The cost of a search is the length of its path, counted in comparisons
In this example, eight insertions build the tree one value at a time. The level list shows the shape they made. The search for 7 walks 8, 3, 6 and 7, paying four comparisons for a tree of eight nodes. The search for 13 walks 8, 10 and 14 and then runs out of nodes. Its path shows the empty slot where an insertion of 13 would land.
Note
Python lists can hold the search path, which makes the walk easy to print and check
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
In the closing example's BST, which path does a search for 4 follow?