0

BST Insert & Search

Medium

Left is smaller, right is larger. That one rule turns search, insert and delete into a single walk down the tree.

ordering invariantlogarithmic
TimeO(h), which is O(log n) when balanced
SpaceO(1) iterative
Inputvalues to insert | value to search
50

50 becomes the root.

1 / 21
insert(node, v):
if node is null: return new Node(v)
if v < node.val: node.left = insert(node.left, v)
else: node.right = insert(node.right, v)
search(node, v): same walk, compare and descend
Why it matters

Inserting sorted data degrades the tree into a linked list. That is why self-balancing trees exist.

Practise this
Validate Binary Search TreeMInsert into a Binary Search TreeMSearch in a Binary Search TreeEDelete Node in a BSTM
Keyboard
space play← → stepr restartctrl K search

More in Binary Search Tree

Validate a BST
O(n)
Next visualiser
Validate a BST