What makes a tree 'balanced'?

In this chapter, we are going to study what makes a tree balanced. We are also going to look at a high-level description of the algorithm used to determine if a given tree is balanced.

Introduction

A binary tree is height-balanced if, for each node in the tree, the difference between the height of the right subtree and the left subtree is at most one.

Height(LeftSubTree)Height(RightSubTree)<=1|Height(LeftSubTree) - Height(RightSubTree) |<= 1

Look at the illustration below of a height-balanced tree. Notice how the left and right sub-trees all appear at the same height.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.