How Do We Get a Balanced Binary Tree?

The Marvel of Binary Trees: Understanding the Basics

What is a Binary Tree?

A Binary Tree is a specialized tree structure where each node has, at most, two child nodes. Interestingly, a binary tree can also be empty, meaning it has zero nodes.

The Recursive Nature of Binary Trees

One of the most intriguing aspects of binary trees is their recursive structure. What does this mean? Well, if you have a rule that applies to the tree, you can also apply that rule to each of its subtrees. In essence, each subtree is a smaller binary tree within the larger structure!

The Heart of a Binary Tree: The Node

To represent a binary tree, you really only need one data structure, aptly called a Node. A node will have: - A Key: The data or value that the node holds. - Left Child: A pointer or reference to the left child node. - Right Child: A pointer or reference to the right child node.

Importance of the Root Node

The root node serves as your gateway to the entire tree. You can traverse to any other node starting from the root. A common pitfall for beginners is losing track of the root node, which makes the entire tree inaccessible. So, it's good practice to maintain a pointer to the root node and ensure it's not modified recklessly in the code.

# Node definition
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

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;
};

class Node {
  Node left, right;
  int value;
  public Node(int value){
    this.value = value;
    left = null; 
    right = null;
  }
}

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class Node {
    public int value;
    public Node left, right;
    Node(int val){
        value = val;
        left = right = null;
    }
}

type Node struct {
    value int
    left *Node  // a pointer to the root of the left subtree
    right *Node // a pointer to the root of the right subtree
}
func NewNode(val int) *Node {
    return &Node{
        value: val,
    }
}

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.., <, >, >=, <=, ==.

0

Binary Search Trees

Binary search trees (or BST for short) are a special case of binary trees, which have an added constraint on the placement of key values within the tree. Very simply, a BST is defined by the following rule:

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

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

If you want to allow duplicate keys to a binary tree, you can do so as long as you be consistent in your implementation. That means you can either always add duplicate nodes to the left, or to the right. But not both in the same tree.

0

Select the false statement about binary search trees.

Balanced BST

A balanced BST is a BST in which the difference in heights of the left and right subtrees is not more than one (1). These example diagrams should make it clear.

Note: Balanced binary tree does not support duplicate keys by default. But if you still want to add duplicates to a balanced binary tree, you can do so by keeping a count of the number of keys in a Node and incrementing it instead of adding a new Node. This is left as side work for you. Post a comment on the discussion if you implemented this!

0

All binary trees can be converted to balanced BST.

The Art of Balancing a Binary Search Tree (BST)

Transforming an unbalanced BST into a balanced one might seem like a daunting task, but it's simpler than you might think. This process gains particular importance when we want to optimize the performance of operations like search, insert, and delete. Specialized trees like Red-Black Trees or AVL trees balance themselves during these operations. But what if you're handed an unbalanced tree to start with?

The Significance of Using an Array

Arrays are a versatile data structure and can be incredibly efficient when it comes to sorting and retrieving data. In the context of balancing a BST, an array serves as a temporary holding place for the tree's elements, sorted in ascending order. Once we have this sorted array, creating a balanced tree becomes a straightforward task.

How We Arrive at This Strategy

Balancing a tree involves ensuring that the left and right subtrees of each node differ in height by at most one. A sorted array inherently satisfies this constraint when converted back into a BST, making it an excellent strategy for our purpose.

The Two-Step Algorithm: Insight and Intuition

Here are the two key steps, along with the intuition behind them:

Step 1: In-Order Traversal into an Array

• What We Do: Perform an in-order traversal of the given unbalanced BST and store each node's value in an array.
• Why We Do It: An in-order traversal of a BST naturally produces a sorted list of its elements. This array now contains all elements of the BST in their proper order but without the baggage of the tree's previous imbalances.

Step 2: Create a Balanced BST from the Sorted Array

• What We Do: Recursively pick the middle element from the sorted array to be the root and repeat the process for the sub-arrays to form left and right subtrees.
• Why We Do It: Choosing the middle element ensures that the tree remains balanced. The left and right halves of the array naturally form the left and right subtrees of each node, maintaining the balanced property.

If you're looking to balance an existing Binary Search Tree (BST), you're in luck. We have a straightforward two-step plan to get you there, leveraging the power of arrays and recursion.

Step 1: The Array

In-Order Traversal: A Journey Through the Tree

In this step, we'll be doing an in-order traversal of the BST and store the nodes in an array. This array will serve as the foundation for building a balanced BST.

• C++ STL’s Vector: In C++, we use the vector data structure from the Standard Template Library (STL) for dynamic array handling.
• Python’s List: In Python, we use the built-in list data structure.

Here, we create a convenience function to do the in-order traversal and store the nodes in an array.

# Convenience function for creating an array from BST in-order traversal
def create_array_from_tree(root, arr):
    if not root: return arr

    arr = create_array_from_tree(root.left, arr)
    arr.append(root.val)
    arr = create_array_from_tree(root.right, arr)

    return arr

// Convenience function for creating an array from BST in-order traversal
vector<int> createArrayFromTree(Node *root, vector<int> arr = vector<int>()) {
    if(root == nullptr) return arr;
    arr = createArrayFromTree(root->left, arr);
    arr.push_back(root->key);
    arr = createArrayFromTree(root->right, arr);
    return arr;
}

// Convenience function for creating an array from BST in-order traversal
public ArrayList<Integer> createArrayFromTree(TreeNode root, ArrayList<Integer> arr) {
    if(root == null) return arr;
    arr = createArrayFromTree(root.left, arr);
    arr.add(root.val);
    arr = createArrayFromTree(root.right, arr);
    return arr;
}

// Convenience function for creating a List from BST in-order traversal
public List<int> CreateArrayFromTree(TreeNode root, List<int> arr = null)
{
    arr = arr ?? new List<int>();
    if(root == null) return arr;
    arr = CreateArrayFromTree(root.left, arr);
    arr.Add(root.val);
    arr = CreateArrayFromTree(root.right, arr);
    return arr;
}

// Convenience function for creating an array from BST in-order traversal
function createArrayFromTree(root, arr=[]) {
    if(root === null) return arr;
    arr = createArrayFromTree(root.left, arr);
    arr.push(root.val);
    arr = createArrayFromTree(root.right, arr);
    return arr;
}

// Convenience function for creating a slice from BST in-order traversal
func createArrayFromTree(root *TreeNode, arr []int) []int {
    if root == nil {
        return arr
    }
    arr = createArrayFromTree(root.Left, arr)
    arr = append(arr, root.Val)
    arr = createArrayFromTree(root.Right, arr)
    return arr
}

Step 2: Crafting the Balanced BST

Breaking Down the Pseudocode

Let’s delve into the pseudocode that describes how we can create a balanced BST from a sorted array. The elegance here is in the recursive nature of the problem and the solution.

Base Case: The Simplest Scenario

1. When the Array is Empty: If the array has no elements, return a null pointer.

Recursive Case: Where the Magic Happens

1. Define a Build Method: This is where you'll craft the balanced tree.
2. Find the Middle: Take the middle element of the array and create a root node with it.
3. Craft the Left Subtree: Call build recursively on the left half of the array. The returned pointer becomes the left child of the root.
4. Craft the Right Subtree: Similarly, call build recursively on the right half. The returned pointer becomes the right child of the root.
5. Return the Root: Finally, return the pointer to the root node you created.

Finding the Middle: The Formula

To find the middle of the array, use the formula (size/2). This assumes a zero-based index, typical in most programming languages.

Before the full implementation, lock in the shape of the algorithm:

1. In-order traversal flattens the BST into a sorted array.
2. Pick the middle value as the root.
3. Recursively repeat for the left and right halves.

The key idea: the sorted array preserves BST ordering, while choosing the middle keeps the tree height small.

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]

First we look at the following array with just one element (i.e. 30).

Array: [31, 37, 38]

Now let's look at an array of size 3.

Array: [10, 11]

Let us now go for an even sized array with two elements.

Array: [10, 11, 17, 19]

We can now extend the example to an even sized array with four elements.

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

An even sized array with eight elements.

0

Now that we understand how balancing works, we can do the fun part, which is coding. We can start the algorithm by creating the array from BST, and calling build function, giving it the starting (0) and ending (n-1) of the array. The full code is given below.

```py
# Node definition
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 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
def build(arr, lower, upper):
    size = upper - lower + 1
    if size <= 0: return None
    middle = size // 2 + lower

    subtree_root = Node(arr[middle])
    subtree_root.left = build(arr, lower, middle - 1)
    subtree_root.right = build(arr, middle + 1, upper)
    return subtree_root

# For convenience, In-order printing a tree
def print_tree(root):
    if root is None: return
    print_tree(root.left)
    print(root.val, " ")
    print_tree(root.right)

# For convenience, we create a right skewed BST.
# This BST will later be balanced.
def array_to_bst(nums):
    if len(nums) == 0: return None

    root = Node(nums[0])

    curr = root
    for i in range(1, len(nums)):
        curr.right = Node(nums[i])
        curr = curr.right
    return root

# Convenience function for creating an array from BST in-order traversal
def create_array_from_tree(root, arr):
    if not root: return arr

    arr = create_array_from_tree(root.left, arr)
    arr.append(root.val)
    arr = create_array_from_tree(root.right, arr)

    return arr

# Build a right skewed tree
root = array_to_bst([10, 11, 17, 19, 30, 31, 37, 38])
# Get the array from the tree
new_arr = create_array_from_tree(root, [])
# Make the skewed tree balanced
new_root = build(new_arr, 0, 7)
# In-order printing to verify
print(print_tree(new_root))
```
```cpp
#include <bits/stdc++.h>

using namespace std;

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;

    Node(int key) : key(key) { }
};

// 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(const vector<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(arr[middle]);
  subtreeRoot -> left = build(arr, lower, middle - 1);
  subtreeRoot -> right = build(arr, middle + 1, upper);
  return subtreeRoot;
}

// For convenience, In-order printing a tree
void printTree(Node *root) {
    if(root == nullptr) return;
    printTree(root->left);
    cout << root->key << " ";
    printTree(root->right);
}

// For convenience, we create a right skewed BST.
// This BST will later be balanced.
Node* buildBSTfromSortedArr(int* arr, int n) {
    if(n == 0) return nullptr;
    Node *root = new Node(arr[0]);

    Node *cur = root;
    for(int i = 1; i<n; i++) {
        cur->right = new Node(arr[i]);
        cur = cur->right;
    }
    return root;
}

// Convenience function for creating an array from BST in-order traversal
vector<int> createArrayFromTree(Node *root, vector<int> arr = vector<int>()) {
    if(root == nullptr) return arr;
    arr = createArrayFromTree(root->left, arr);
    arr.push_back(root->key);
    arr = createArrayFromTree(root->right, arr);
    return arr;
}

int main() {
    int arr[] = {10, 11, 17, 19, 30, 31, 37, 38};
    int n = 8;
    // Build a right skewed tree
    Node* root = buildBSTfromSortedArr(arr, n);
    // Get the array from the tree
    vector<int> newArr = createArrayFromTree(root);
    // Make the skewed tree balanced
    Node* newRoot = build(newArr, 0, n-1);
    // In-order printing to verify
    printTree(newRoot);
    return 0;
}
```
```java
class Node {
  Node left, right;
  int key;

  public Node(int item) {
    key = item;
    left = right = null;
  }
}

class BinarySearchTree {
  Node root;

  Node build(int arr[], int start, int end) {
    if (start > end) {
      return null;
    }
    int mid = (start + end) / 2;
    Node node = new Node(arr[mid]);
    node.left = build(arr, start, mid - 1);
    node.right = build(arr, mid + 1, end);
    return node;
  }

  void preOrder(Node node) {
    if (node == null) {
      return;
    }
    System.out.print(node.key + " ");
    preOrder(node.left);
    preOrder(node.right);
  }
  
  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    int arr[] = new int[]{10, 11, 17, 19, 30, 31, 37, 38};
    int n = arr.length;
    tree.root = tree.build(arr, 0, n - 1);
    tree.preOrder(tree.root);
  }
}
```
```javascript
class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

function arrayToBST(arr) {
  if (!arr.length) return null;
  let mid = Math.floor(arr.length / 2);
  let root = new Node(arr[mid]);
  root.left = arrayToBST(arr.slice(0,mid));
  root.right = arrayToBST(arr.slice(mid+1));
  return root;
}

function preOrder(node) {
  if (node) {
    console.log(node.data);
    preOrder(node.left);
    preOrder(node.right);
  }
}

let arr = [10, 11, 17, 19, 30, 31, 37, 38];
let root = arrayToBST(arr);
preOrder(root);
```
```csharp
class Node {
    public int data;
    public Node left, right;
  
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    static Node root;

    Node sortedArrayToBST(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;
        Node node = new Node(arr[mid]);
        
        node.left = sortedArrayToBST(arr, start, mid - 1);
        node.right = sortedArrayToBST(arr, mid + 1, end);
        
        return node;
    }
  
    void preOrder(Node node) {
        if (node == null) {
            return;
        }
        Console.Write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
  
    public static void Main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int[] arr = new int[] {10, 11, 17, 19, 30, 31, 37, 38};
        int n = arr.Length;
        root = tree.sortedArrayToBST(arr, 0, n - 1);
        Console.WriteLine("Preorder traversal of constructed BST");
        tree.preOrder(root);
    }
}
```
```go
package main

import "fmt"

type Node struct {
  data int
  left *Node
  right *Node
}

func sortedArrayToBST(arr []int) *Node {
  if len(arr) == 0 {
    return nil
  }
  mid := len(arr) / 2
  root := &Node{data: arr[mid]}
  root.left = sortedArrayToBST(arr[:mid])
  root.right = sortedArrayToBST(arr[mid+1:])
  return root
}

func preOrder(n *Node) {
  if n == nil {
    return
  }
  fmt.Printf("%d ", n.data)
  preOrder(n.left)
  preOrder(n.right)
}

func main() {
  arr := []int{10, 11, 17, 19, 30, 31, 37, 38}
  root := sortedArrayToBST(arr)
  preOrder(root)
}
```

The code is doing one repeated move: choose the middle index, create a node, then recurse on the two remaining ranges.

When reading the Java version, track lower, upper, and middle. Each recursive call owns a smaller slice of the sorted array, and each slice becomes one subtree.

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.

Complexity of the Algorithm

The previous code has a complexity of O(N), where N is the number of nodes in the tree.

Inorder traversal requires O(N) time. As we are accessing each element of the array exactly once. After that, we are calculating the median value of the array, breaking it into two halves, and again calculating the median. This will take O(logN) time. Finally, the build method also has a time complexity of O(N).

So the total time complexity would be O(N+logN+N) ~ O(N).

We are creating an array of size N. And then again creating a binary tree of size N. And also, keep in mind that this is a recursive call that is called twice with half the data of the first call. So it will take a memory of O(logN).

So the total memory complexity would be O(N+N+logN) ~ O(N) as well.

An odd sized array with 5 elements cannot be converted to a balanced BST.

It is possible to convert a BST to balanced BST without using recursion, and it will have better time complexity than the recursive approach.

One Pager Cheat Sheet

• A binary tree is a recursive structure composed of one Node with a key value and up to two child Nodes that can be traversed with a root pointer.
• A BST is a special type of binary tree where the key values are placed according to a defined rule; nodes in the left subtree have keys less than the parent, and keys in the right subtree have keys greater than the parent.
• Every node in a binary search tree at most has two children and duplicates can be added, but must be placed in the same subtree.
• A balanced BST is a Binary Search Tree in which the left and right subtrees differ in height by no more than 1.
• A binary tree can be rebalanced to become a balanced BST, thereby ensuring that all subtrees of a given node will differ in height by no more than one (1).
• Create a balanced BST tree from a sorted array based on the in-order traversal of the unbalanced tree for efficient balancing.
• We are creating an array from BST in-order traversal using a vector and also recursively creating a balanced BST using build method with the middle array element being the root node.
• - Balance a BST by converting it to a sorted array, then recursively choosing middle elements as subtree roots.
• We are building a balanced binary tree from arrays of different lengths to view the pseudo code in action.
• We can start balancing our BST by coding the build function, with 0 and n-1 as its starting and ending parameters, respectively.
• - In build(arr, lower, upper), each recursive call turns one array range into one subtree.
• Before trying out the code, it is best to conduct a dry run to get an idea of the time and memory complexities (which are O(N)) of the inorder traversal algorithm.
• It is possible to convert an array into a balanced Binary Search Tree (BST) using inorder traversal to divide the array and create a root node and subtrees that differ in height by one.
• It is not possible to convert a BST to a balanced BST without using recursion, as there is no algorithm known to have a better time complexity than O(n log n).