Binary Search Tree (BST)


A Binary Search Tree is a node-based binary tree data structure which has the following properties:



To insert a new node, start from the root and compare it with the key:

  1. If the new key is less, go to the left child.
  2. If the new key is more, go to the right child.
  3. Repeat until the correct leaf node is found for insertion.


Deletion in a BST can be more complex and requires three cases to consider:

  1. Deleting a leaf (node with no children).
  2. Deleting a node with one child.
  3. Deleting a node with two children.
Diagram of a Binary Search Tree

Learn More

For more information on Binary Search Trees, visit Wikipedia.