educative.io

Example of balanced binary tree

Courses
,
#1

I don’t understand quite why the example of the whether the binary tree is balanced is actually unbalanced.

The left subtree root is 2. At this level, the HLT is 2. And the right subtree root is 3 and at this level the HRT is 2. So at the root node, which is 1, the HLT and HRT are 3 and 3 each. By the definition the difference of HLT - HRT is 0 and hence it should be balanced. So, why is the answer unbalanced ?

Course: Data Structures for Coding Interviews in Java - Learn Interactively
Lesson: What Makes a Tree Balanced? - Data Structures for Coding Interviews in Java

#2

Hi @Ajay,

Let’s look at the case of node 2:

HLT for node 2 is = 2
HRT for node 2 is = 0

2-0 = 2, means node 2 is not satisfying the condition and the tree becomes unbalanced. We’ve to check the balance condition for each node. If all nodes satisfy the condition, then the tree is balanced.

#3

Thanks for the response. I now understand that the condition HLT- HRT <=1 should be applicable for every node and not just the root node. If one of the subtree root nodes does not satisfy, then I dont even have to reach the root node.

Course: Data Structures for Coding Interviews in Java - Learn Interactively
Lesson: More on Complete Binary Trees - Data Structures for Coding Interviews in Java

2 Likes
#4

Thanks man. I was first confused too. They could’ve given a better illustration so it’s clear that the the formula should be applicable for every node and not just the root

1 Like