BST Insertion

Insert values into a Binary Search Tree one at a time. At each node, go left if the new value is smaller, right if larger — place it in the first empty slot.

time O(h) per insert (O(log n) balanced, O(n) worst)

space O(h)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

insert(root, v):
  if root == null: return Node(v)
  if v < root.value: root.left  = insert(root.left, v)
  else:              root.right = insert(root.right, v)
  return root