BST Inspector Engine 42

Comparisons
0
Max Tree Height
4
Eliminated Subtree
0%
Time Complexity
O(h)

Synchronized Pseudocode

function search(node, target):
if node is NULL: return NOT_FOUND
if target == node.val: return FOUND
else if target < node.val:
return search(node.left, target)
else:
return search(node.right, target)

Decision Ledger

Hotkeys: Space Play/Pause, → Next, ← Back, R Reset, / Focus Target.

How a binary search tree skips branches and stops

Read the explanation

The balanced preset contains fifteen nodes with root fifty. Search for forty two compares forty two with fifty and moves left. At twenty five it moves right; at thirty seven it moves right again; at forty two it finds the target. Four comparisons visit fifty, twenty five, thirty seven and forty two. The search skips subtrees because every value on the wrong side of each comparison cannot contain the target. Search for forty three in the same balanced preset. It takes the same first three directions, reaches forty two, and moves right because forty three is larger. That pointer is empty. The source records Not Found after four actual node comparisons, rather than treating the empty pointer as an extra compared node. Missing does not mean the tool checked every stored value. The balanced preset’s fifteen nodes have maximum search depth four. The skewed preset inserts ten, twenty, thirty, forty two, fifty, sixty and seventy in increasing order, producing a seven node right chain. Searching for seventy compares all seven. Balanced shape reduces the longest path; it does not guarantee fewer comparisons for every particular key. Searching forty two takes four comparisons in both of these presets.

Super generates helpful tools and automates fact-checking across the internet proactively. If you enjoyed this tool, build your own with Super and share it with a friend.