How Do We Get a Balanced Binary Tree?

Jake Zhang
Aug 24, 2020 · 6 min read

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.

Image for post
Image for post

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 allows comparison operators, i.e.., <, >, >=, <=, ==.

Binary Search Trees

  • All nodes in the left subtree have key values less than or equal to the key value of the parent
  • All nodes in the right subtree have key values greater than or equal to the key value of the parent

The figure below shows an example of a binary search tree:

Image for post
Image for post

Balanced BST

Image for post
Image for post
Image for post
Image for post

How to Balance a BST

However, when given an unbalanced tree, how do you convert it to a balanced tree in an efficient manner? There is one very simple and efficient algorithm to do so by using arrays. There are two steps involved:

  1. Do an in-order traversal of the BST and store the values in an array. The array values would be sorted in ascending order.
  2. Create a balanced BST tree from the sorted array.

So there’s two steps in our plan so far:

Step 1: In-order Traversal

Step 2: Create a balanced BST

Let’s explore them. Pseudo-code to efficiently create a balanced BST is recursive, and both its base case and recursive case are given below:

Base case:

Recursive case:

  1. Get the middle of the array and make it the root node.
  2. Call the recursive case build on the left half of the array. The root node’s left child is the pointer returned by this recursive call.
  3. Call the recursive case build on the right half of the array. The root node’s right child is the pointer returned by this recursive call.
  4. Return a pointer to the root node that was created in step 1.

The above pseudo-code’s elegance stems from the fact that the tree itself is recursive. Thus, we can apply recursive procedures to it. We apply the same thing over and over again to the left and right subtrees.

You may be wondering how to get the middle of the array. The simple formula (size/2) returns the index of the middle item. This of course assumes that the index of the array starts from 0.

Let’s look at some examples to see how the previous pseudo code works. We’ll take a few simple scenarios and then build a more complex one.

Array: [30]

Image for post
Image for post

Array: [31, 37, 38]

Image for post
Image for post

Array: [10, 11]

Image for post
Image for post

Array: [10, 11, 17, 19]

Image for post
Image for post

Array: [10, 11, 17, 19, 30, 31, 37, 38]

Image for post
Image for post

Now that we understand how balancing works, we can do the fun part, which is coding. Here is the C++ helper function, which is the recursive routine build that we had defined earlier.

The code below shows how you can call the above helper recursive function build:

void build(int *arr, int size, binaryTree &tree) {
tree.root = build(arr, 0, size-1);
}

Here’s. the final code:

// build returns a pointer to the root node of the sub-tree
// lower is the lower index of the array
// upper is the upper index of the array
node * build(int * arr, int lower, int upper) {
int size = upper - lower + 1;
// cout << size; //uncomment in case you want to see how it's working
// base case: array of size zero
if (size <= 0)
return NULL;
// recursive case
int middle = size / 2 + lower;
// make sure you add the offset of lower
// cout << arr[middle] << " "; //uncomment in case you want to see how it's working
node * subtreeRoot = new node;
subtreeRoot - > key = arr[middle];
subtreeRoot - > left = build(arr, lower, middle - 1);
subtreeRoot - > right = build(arr, middle + 1, upper);
return subtreeRoot;
}

Before trying out the above code, it is always best to sit down with a paper and pen, and conduct a dry run of the code a few times to see how it works. The previous code has a complexity of O(N), where N is the number of keys in the tree.

Inorder traversal requires O(N) time. As we are accessing each element of the array exactly once, the build method thus also has a time complexity of O(N).

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

The Startup

Medium's largest active publication, followed by +755K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store