DataStructures Series #13 – Binary Search Tree Datastructure

Trees, Binary trees and Binary search trees. » Learn Over Coffee

Image source: https://learnovercoffee.com/

A binary tree is a tree with every node having at most two children.

Example of a binary tree
Image source: https://en.wikipedia.org/

Please note that the node keys in the binary tree above isn’t arranged in any specific order. The only rule required is that every node has at most two children.

The Binary Search Tree is a type of Binary Tree datastructure that keeps its nodes keys in sorted order, lesser keys to the left and greater keys to the right.

Example of a binary search tree
Image source: https://en.wikipedia.org/

This arrangement enhances operations on the tree to be done using the binary search principle. The binary search principle searches for a node, starting from the root node and comparing between the left and right nodes to decide the next node to visit all the way down to the leaf node until it finds the search node.

Search Implementation

Search implementation pseudocode

// Node structure
class Node {
  Node left;
  Node right;
  int data;
}

search (int searchData, Node node) {
   if (node == null or node.data == searchData) {
      return node;
   }

   if (searchData < node.data) {
      return search(searchData, node.left);
   }
   
   if (searchData > node.data) {
     return search(searchData, node.right);
   }
}

REFERENCES