Balanced Binary Tree

Contents

Balanced Binary Tree#


Question Number Difficulty Tag Tag Tag Tag

TODO#

This question is not as easy as it seems. Read the solution and understood why you need \(-1\) as well as return max(left, right) + 1 in the recursive function.

To revisit.

Let’s consider our running example.

 1tree_values: List[Union[int, None]] = [
 2    1,
 3    2,
 4    4,
 5    None,
 6    7,
 7    None,
 8    None,
 9    5,
10    None,
11    None,
12    3,
13    None,
14    6,
15    8,
16    None,
17]
18
19root = build_binary_tree_from_list_preorder(tree_values)
20lines = print_binary_tree(
21    root, node_info=lambda n: (str(n.value), n.left, n.right), is_top=False
22)
23rich.print("\n".join(lines))

    1
   / \
  2   3
 / \   \
4   5   6
 \     /
  7   8

Intuition#

Some intuition first on whether to use top-down or bottom-up approach (i.e. preorder vs postorder).

You want the parent to ask: can you both child check if you are balanced.

Contents