How Do We Get a Balanced Binary Tree?

A binary tree, as the name suggests, is any tree in which each node has at the most two child nodes. A binary tree can be empty, implying zero nodes in the tree. The cool thing about binary trees is that they are recursive structures. This means a rule can be applied to the entire tree by applying it turn by turn to all of its subtrees.

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

To define a binary tree, we need two data structures. One would be the overall binary tree structure that keeps track of the root node. The other would be the node structure that keeps track of the left and right subtrees.

class binaryTree {
  public:
    node * root; //a pointer to the root
};

Now let’s define the node structure, which would keep track of both left and right child nodes, and contain a piece of data, which in this case we call the key.

class node {
  public:
    node * left; //a pointer to the root of the left subtree
    node * right; //a pointer to the root of the right subtree
    int key;
};

Here, we are assuming that key data type is an integer, just to keep things simple. But it should be noted that the key type can be any data structure which…