While I was practicing data structures problems I stumbled upon the problem how to find the height of the tree and check if the tree is a balanced tree. Why do we need this balancing? What do we mean by balance?
First of all, many data structures have a balance invariant. Depending on the data structure, accomplishing balance will be achieved by different means. Consider skewed Binary Search Tree, where all nodes (besides leaf) have only right child and left child is always null. Runtime complexity of find() on this tree would be O(n).
In order to achieve better performance you need to balance the tree. From the definition the perfectly balanced tree is when the left and right subtrees of any node are of the same height. We are talking about almost perfectly balanced tree if the subtrees’ height differ by at most 1. Balancing a BST guarantees O(log n) search time.
Problem: Checking if a BST is a balanced tree.
// Having Node definition
function Node(val, left, right) {
return {val, left, right}
}// Build a sample tree
let BSTtree = Node(1, Node(2, Node(3, null, null), Node(4, null, null)), Node(5, null, Node(6, null, null)))
- In order to check if a given tree meets the balance property, first you’ll need a logic to get the height of a tree.
const height = function (root) {
if (root === null) {
return 0
}
let leftHeight = height(root.left)
let rightHeight = height(root.right)
return Math.max(leftHeight, rightHeight) + 1
}//A tree node’s height is defined as the number of edges on the longest path to a leaf. A leaf node’s height is 0.
2. When you have a height, check if the branches of the tree are balanced.
//A tree is balanced if for every node, height difference for left and right child is at most 1
// an empty tree is balancedconst isBalanced = function (root) {
// step 1 - empty tree is balanced! if (root === null) {
return true
}
// step 2 - verify is children are balanced and if not return it immediatelylet areChildrenBalanced = isBalanced(root.left) && isBalanced(root.right) if (!areChildrenBalanced) return false; // step 3 - we know children are balanced, time to verify if current node is balanced let leftHeight = height(root.left)
let rightHeight = height(root.right)
let diff = Math.abs(leftHeight — rightHeight) return Math.abs(leftHeight — rightHeight) <= 1
}
