Binary Search Tree

A Binary Search Tree (BST) is a binary tree where each node has at most two children, and the left subtree contains values less than the node, while the right subtree contains values greater than the node.

Binary Search Tree Visualization

Traversals:
Extras:
SlowFast
🔊 Sound
ReadyEmpty BST. Insert a value to begin.
● Search/insert path● Found / target● Active node● Traversal● Min / Max● Default
empty BST — insert a value

Complexity

Time Complexity: O(log n) average, O(n) worst for search/insert/delete
Space Complexity: O(n)

Pseudocode

class BSTNode:
  value: data
  left: left child
  right: right child
  
function insert(root, value):
  if root is null:
    return new BSTNode(value)
  
  if value < root.value:
    root.left = insert(root.left, value)
  else:
    root.right = insert(root.right, value)
  
  return root