Binary Search Tree Insertion in C++

This article will demonstrate how to implement the insert function for binary search tree data structure in C++.

Insert New Nodes in Binary Search Tree in C++

Binary trees represent a subset of tree structures generally. They are called binary because of having at most two children at any given node. In this case, we discuss a binary search tree where each node contains a data member called a key, and at every level of the tree, the given node’s key must be greater than keys in its left subtree and less than all keys in the right subtree. This feature will allow us to use a binary search algorithm on the tree as we search in a sorted array.

At first, we need to declare a tree node struct, which includes two pointers to left/right nodes and a key. For the sake of simplicity, we are storing keys as int values, but one may need to construct a different layout for the node depending on the problem. We also construct this tree manually by declaring a single TreeNode pointer as the root of the tree and then calling the insertNode function to add new nodes.

For better demonstration and verification of our example, we also include a function to find a node with the given key and another to print the contents of the whole tree. The latter will help us easily inspect the tree structure at each step of the program. Notice that all three functions utilize recursion as a tree structure is inherent to divide and conquer algorithms.

#include <iostream>
#include <vector>

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

struct TreeNode {
  int key;
  struct TreeNode *left{};
  struct TreeNode *right{};
};

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

TreeNode *findNode(TreeNode *root, const int 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 printTree(TreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};

  TreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }
  printTree(root);
  cout << endl;

  std::vector<int> v2{1, 22, 4, 16};
  for (const auto &item : v2) {
    insertNode(root, item);
  }
  printTree(root);
  cout << endl;

  return EXIT_SUCCESS;
}

Output:

2; 3; 5; 9; 11; 15; 20; 23;
1; 2; 3; 4; 5; 9; 11; 15; 16; 20; 22; 23;

In the main function, we declare two arbitrary int vectors and then push their elements to the tree. Note that our insertNode function takes two parameters - root node and a key value. It needs to check if the given root node is valid or just a nullptr, the latter of which indicates that the function needs to create root node contents.

If the root node is already initialized, then the function should proceed according to the key value, which is compared to the current node’s key. If the key’s value passed is less than the given key, we should move forward to the left subtree. Otherwise - the right subtree.

Eventually, we will reach the node where the key needs to be stored, and the inorder traversal will always print the sorted key values as demonstrated in the code snippet.