Balanced Binary Tree – Definition, How to Check, Time & Space Complexity Vijay Sinha The Crazy Programmer
In this article, we take a look into an important type of Binary Tree based Data Structure – Balanced Binary Tree. We will discuss the description of balanced binary trees with examples. Along with this, we will also look at an interesting problem related to it. Definition A Balanced Binary Tree commonly referred to as Height-Balanced Binary Tree, is a binary tree in which the depth of the two subtrees on either side of every node never differs by more than 1 . For any node, the difference in height for its left and right subtrees respectively does not exceed 1. The height difference can have a value either 0 or 1. The tree is said to be balanced if the height of the tree is maintained at Log n at every instant, for n nodes in a tree. Similarly, a Binary Search Tree that follows the above condition is a Balanced Binary Search Tree or Balanced BST. So, to summarize in Balanced BST: The difference in height of left and right subtrees must not exceed 1. And, the left subtree and