Balanced Binary Tree

Try to solve the Balanced Binary Tree problem.

We'll cover the following

Statement#

Given a binary tree with nn nodes, return TRUE if it is height-balanced. Otherwise, return FALSE.

Note: The height of an empty tree is 00.

Constraints:

  • 1≤n≤5001 \leq n \leq 500
  • −104≤-10^4 \leq Node.data ≤104\leq 10^4

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Balanced Binary Tree

1

Given the below binary tree, what is the output?

  5
 / \
4   8
   / \
  7   9
       \
        10
A)

TRUE

B)

FALSE

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Start traversing the tree using the postorder traversal.

For each node, calculate the height of its left and right subtrees.

Check if the difference between the heights of its left and right subtrees is greater than 1. If it is, return FALSE because this subtree is not balanced.

If the difference between the heights of left and right subtrees of all nodes is less than or equal to one, it signifies that the tree is balanced. Therefore, we return TRUE.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
%0 node_1 6 node_2 2 node_1->node_2 node_3 8 node_1->node_3 node_4 0 node_2->node_4 node_5 4 node_2->node_5 node_10 3 node_5->node_10 node_11 5 node_5->node_11 node_6 7 node_3->node_6 node_7 9 node_3->node_7
Visualization for Input #1
Balanced Binary Tree

Solution: Serialize and Deserialize Binary Tree

Solution: Balanced Binary Tree