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

Binary Search Tree is empty

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