How to Implement the Binary Tree Data Structure in C++

1. Implement the Binary Tree Using the struct Keyword in C++
2. Implement Functions to Calculate the Size and the Height of the Tree Structure and A Function to Print Elements in C++

This article will explain how to implement the binary tree data structure in C++.

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

Trees are abstract data structures utilized in various fundamental algorithms. They are generally hierarchical structures where there needs to be a root node and its children forming subtrees. Also, there are multiple tree structure types, each suited for particular needs and providing some trade-offs.

A binary tree is one of the subclasses of tree data structures, and it’s defined as a tree where each node must have two children at most, including children nodes designated as left and right. In this case, we implement a binary tree using the struct function since it declares a class where members are public by default. A node in a binary tree contains two pointers to the left/right nodes and the data as needed. Note that we declared a single int member to represent the data stored at the node for explanation purposes only.

We define a constructor that takes an integer as the argument and initializes the data member with its value. Then, it initializes the two-node pointers with nullptr values, which is a common way to denote the leaf nodes. The example driver code constructs a sample graph and stores random integers in each node. There are multiple sub-types of binary trees, e.g., a full binary tree is a structure where every node has 0 or 2 children. Another one is called a perfect binary tree, where all interior nodes have two children, and all the leaf nodes have identical depths.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  root->left = new BinTreeNode(distr(eng));
  root->right = new BinTreeNode(distr(eng));
  root->right->left = new BinTreeNode(distr(eng));
  root->right->right = new BinTreeNode(distr(eng));

  return EXIT_SUCCESS;
}

Notice that the above code results in a full binary tree structure, as displayed in the following graph. We allocated each node using the new operator and passed an initializer value using the pseudo-random number generator.

root / left right / \ / nullptr nullptr left right /   \ /
    nullptr nullptr nullptr nullptr

Implement Functions to Calculate the Size and the Height of the Tree Structure and A Function to Print Elements in C++

Since the tree structure is the form in which divide and conquer algorithms execute, the latter method is often utilized to implement the functions that manipulate their elements. The treeSize function retrieves the size of the tree that denotes the number of all nodes, including the root. Notice that we only need to use a simple recursion and return the size of the root value (which is 1) plus the sizes of the left/right nodes.

The next function is treeHeight that retrieves the height of the tree, which is generally known as the amount of nodes in the longest path from a root to a leaf. This function also utilizes the recursion by calling itself on both children nodes and returning the height of the root value (which is 1) plus the larger value from the previous calls.

On the other hand, the printData function outputs the data member from each node to the cout stream. There are multiple traversal ways for the binary tree structure: inorder, preorder, and postorder traversal.

In the following example, the inorder traversal way is utilized. The process prints the data from the leftmost leaf nodes going to the right on the same depth at first and then moves to the upper levels. The next code snippet constructs a partially random binary tree and then calls each of the above functions on it. If the recursive nature of these functions appears to be confusing at first look, you should try debugging them step-by-step on the smaller tree objects and observe the behavior on each recursive function call.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

int treeSize(BinTreeNode *n) {
  if (n == nullptr)
    return 0;
  else
    return 1 + treeSize(n->left) + treeSize(n->right);
}

int treeHeight(BinTreeNode *n) {
  int lh, rh;

  if (n == nullptr)
    return -1;
  else {
    lh = treeHeight(n->left);
    rh = treeHeight(n->right);
    return 1 + (lh > rh ? lh : rh);
  }
}

void printData(BinTreeNode *n) {
  if (n != nullptr) {
    printData(n->left);
    cout << n->data << "; ";
    printData(n->right);
  }
}

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  auto tmp = root;

  auto iter = 100;
  while (iter > 0) {
    auto val = distr(eng);
    if (val % 5 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
      tmp = tmp->left;
    } else if (val % 4 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
      tmp = tmp->right;
    } else if (val % 6 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
    } else if (val % 100 == 0) {
      tmp = root;
    } else if (val % 2 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
    }
    iter -= 1;
  }

  cout << "size of tree = " << treeSize(root) << endl;
  cout << "height of tree = " << treeHeight(root) << endl;
  printData(root);

  return EXIT_SUCCESS;
}

Output:

size of tree = 45
height of tree = 37
...(elements in the tree)