How to Implement a Binary Search Tree Data Structure in C++

1. Implement a Binary Search Tree Using the struct Keyword in C++
2. Implement the Binary Search Algorithm for a Binary Search Tree in C++

This guide will demonstrate how to implement a binary search tree data structure in C++.

Implement a Binary Search Tree Using the struct Keyword in C++

A binary search tree (BST) is a special case of a binary tree data structure. The data structure is usually utilized to store a sorted list of elements for fast searching using the binary search algorithm. In contrast to the regular binary tree, BST has a special data member in each node called a key, which must have unique values.

Every node in a BST should satisfy the following requirement: the key value must be greater than all the keys in the subtree of its left child and less than all the keys in the subtree of its right child. The previous statement implies that the elements with lesser key values will be positioned on the left side of the tree hierarchy; this results in an optimal structure to use binary search on.

In the following example code, we define a struct named BSTreeNode, consisting of two pointers to the left/right nodes and a string member to denote the key. Notice that we are just implementing the simplest version of BST, where the key value is the same as the data stored in the node.

Generally, the programmer is free to define a BST node to store other data members as needed for the specific problem. This definition is best suited to emulate the sorted array of strings, which needs to be searched for a given string(key). Before we implement the binary search function, the BST object needs to be constructed from scratch. Thus, we use a predefined vector of strings to initialize a new binary search tree.

The insertNode function is the recursive implementation to create a new child BSTreeNode when the root of the tree is passed as the argument. If we need to create a root node itself, you can declare a pointer to the BSTreeNode type, assign nullptr to it, and pass it to the insertNode with the corresponding string value that needs to be stored there. Once we initialized the list with v1 contents, the printTree function can be invoked to print all key values in the sorted order called the inorder traversal of BST.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

void printTree(BSTreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printTree(root);

  return EXIT_SUCCESS;
}

Output:

aim; born; camel; maya; wind; xen; zero;

Implement the Binary Search Algorithm for a Binary Search Tree in C++

The binary search algorithm is efficient on the BST structure because of the ordering, where the keys are stored in the hierarchy. There are three main operations implemented for the BSTs: insertion, deletion, and lookup.

In the following example, we are focusing more on the lookup. The findNode function is responsible for the lookup of the given key in the BST, which is passed to a function using its root node. This command is of a recursive nature and returns the pointer to the BSTreeNode where the key is stored. If the key value is not found in any nodes, nullptr is returned. For better demonstration, we also implemented a printNode function that takes the node pointer and outputs the key value to the cout stream to chain the findNode function return value directly in the function to print it.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

BSTreeNode *findNode(BSTreeNode *root, const string &k) {
  if (root == nullptr) return nullptr;

  if (k == root->key) return root;

  if (k < root->key)
    return findNode(root->left, k);
  else
    return findNode(root->right, k);
}

void printNode(BSTreeNode *n) {
  if (n != nullptr) {
    cout << n->key << endl;
  } else {
    cout << "Not a valid node!" << endl;
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printNode(findNode(root, "zero"));
  printNode(findNode(root, "zeroo"));

  return EXIT_SUCCESS;
}

Output:

zero
Not a valid node!