Is there a trick to solve binary tree problems with `size` or `height`?

Question

About binary trees, I understand the difference between size and height: size is the number of nodes while height of a tree is the max number of edges from the root to the furthest leaf.

However, when dealing with problems involving height, my mind is often twisted and can't think straight.

For the following two problems, they are very similar except one with constraints on size while the other one with height.

For example, let's first have the one involving size.

In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function to construct all possible completely balanced binary trees for a given number of nodes - n. The function should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

This problem is to generate all possible completely balanced binary tress as long as the property is held.

I think size is simple. What I can do is like this:

Using recursion
If n mod 2 = 1, then generate all such trees with n=n/2, then merge every pair of those trees with a new root.
If n mod 2 = 0, then generate one set of trees with n/2 and another set of trees with n/2-. then merge every pair (one from a set) with a new root, also don't forget to exchange the elements inside every pair.
If n = 0 then return a set with only one Leaf
If n = 1 then return a set with only one singleton internal node with two Leaves.

When the size in the problem is changed to height, I don't really know how to cleverly think any more.

In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.

Write a function to construct all possible height-balanced binary trees for a given number of nodes - n. The function should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

I think if involving height, things get quite arbitrary.

Is the solution for the 2nd problem is the same as the 1st problem?

How really should I train myself to handle the height thing? Where is the trick?

Bernhard Barker Bernhard Barker · Accepted Answer · 2014-02-20T11:37:36

No, it's not the same. Consider: (each node's value indicates the height of its subtree)

     4
   /   \
  2     3
 /     / \
1     2   2
     / \ / \
    1  1 1  1

The left subtree has 2 nodes, the right has 7, yet it is height-balanced.

The first thing you need to do is calculate both the minimum and the maximum number of nodes for some given height (the maximum is simply 2^n-1, the minimum can be calculated iteratively starting from height 1, or perhaps there's also a formula for that).

Then you need to loop through the heights for the left subtree and the right subtree (which will be the height of the left subtree + 1/0/-1), if we can get to n using these heights, that is: the maximum number of nodes for these heights plus one is >= n and the minimum number of nodes for these heights plus one is <= n, loop through all combinations adding up to n, generating all valid trees, and merging them, similarly to what you did for the first problem.

I hope that makes sense.

There's no real trick to dealing with problems involving heights - the approach would vary greatly from problem to problem. It's usually important to keep in mind that the height of a balanced tree is ~log₂n and that a complete tree of height n has 2^n-1 nodes.

Is there a trick to solve binary tree problems with `size` or `height`?

1 Answers