The answer is: 2357

I provide here a reasoned approach (no programming involved) and code to produce the same result, but via a more brute-force method.

A. Reasoning

Intuitively, it seems easier to count by exclusion. So that leads to this approach:

• Count all the binary trees with 9 nodes. As you already indicated, this corresponds to the 9^th Catalan number. This is C₉ = 4862.
• Subtract the number of trees whose roots are balanced, i.e. where the two subtrees of the root have equal heights (let's call those subtrees L and R). That gives us the number of trees that are either left- or right-heavy.
• As there are just as many left- as right-heavy trees, divide this result by two to get the final result.

So now we can focus on calculating the number mentioned in the second bullet point:

Counting trees that are strictly balanced at the root

A tree of height 2 would have at most 7 nodes (when it is full), so the height needs to be at least 3. A tree of height 5 (that is balanced at the root) needs at least 5 nodes in A (on a single path), and 5 in B (also on a single path), so the height cannot be more than 4. We thus have only two possibilities: the height of a 9-node binary tree, that is balanced in the root, is either 3 or 4.

Let's deal with these two cases separately:

1. When the height of the tree is 3

In this case we have a tree with 4 levels. Let's analyse each level:

There are 3 nodes in the first two levels: the root and its two children.

The third level is the first level where there can be some variation: that level has between 2 and 4 nodes. Let's deal with those three cases one by one:

1.a Third level has 2 nodes

Here the third level has one node in L and one in R. Each can either be a left or right child of its parent. So there are two possibilities at either side: 2x2 = 4 possibilities.

There is no variation possible in the fourth level: the four remaining nodes are children of the two nodes in the third level.

Possibilities: 4

1.b Third level has 3 nodes

There are 4 ways to select three positions from the four available positions in the third level. Either L or R gets only one node. Let's call this node x.

In the fourth level we need to distribute the three remaining nodes, such that L and R get at least one of those. This is achieved when x gets either one or two children.

• When x gets two children, the other remaining node has 4 possible positions. Here you see those 4 positions in light grey:

• When x gets one child, it can be either a left or right child, and the other two remaining nodes can occupy the four available positions (see image above) in 6 ways: 2x6=12.

So given a choice in the third level, there are 4+12=16 possible configurations for the fourth level.

Combining this with the possibilities in the third level, we get 4x16:

Possibilities: 64

1.c Third level has 4 nodes

The third level is thus full. The two remaining nodes on the fourth level need to be split between L and R, and so each has 4 possible positions. This gives 4x4 = 16 possibilities in total.

Possibilities: 16

2. When the height of the tree is 4

When the height is 4, then by consequence L and R each have only one leaf: they are chains of 4 nodes each. This is the only way to make the root strictly balanced and get a height of 4.

There is no choice for the root node of L (it is the left child of the root), but from there on, each next descendant in L can be either a left or right child of its parent. The shape of L has thus 2³ possibilities = 8. Considering the same for R, we have a total of 8x8 = 64 shapes.

Possibilities: 64

Total

Taking all of the above together, we have 4+64+16 + 64 = 148 possible shapes that give a tree with a balanced root.

So applying the approach set out at the top, the total number of left-heavy binary trees with 9 unlabelled nodes is (4862-148)/2 = 2357

B. Code

To make this a programming challenge, here is an implementation in JavaScript that defines the following functions:

• countTreesUpToHeight(n, height): count all binary trees with n nodes, that are not higher than the given height. Uses recursion.

• countTreesWithHeight(n, height): count all binary trees with n nodes, that have exactly the given height. Uses the preceding function.

• countLeftHeavy(n): the main function. Uses the other two functions to count all combinations where the root's left subtree is higher than the right one.

So this approach is not like the exclusion approach above. It actually counts the combinations of interest. The output is the same.

function countTreesUpToHeight(n, height) {
    if (n > 2**(height+1) - 1) return 0; // too many nodes to fit within height
    if (n < 2) return 1;
    let count = 0;
    for (let i = 0; i < n; i++) {
        count += countTreesUpToHeight(i, height-1) 
               * countTreesUpToHeight(n-1-i, height-1);
    }
    return count;
}

function countTreesWithHeight(n, height) {
    return countTreesUpToHeight(n, height) - countTreesUpToHeight(n, height-1);
}

function countLeftHeavy(n) {
    let count = 0;
    // make choices for the height of the left subtree
    for (let height = 0; height < n; height++) {
        // make choices for the number of nodes in the left subtree
        for (let i = 0; i < n; i++) {
            // multiply the number of combinations for the left subtree 
            //   with those for the right subtree 
            count += countTreesWithHeight(i, height-1)
                   * countTreesUpToHeight(n-1-i, height-2);
        }
    }
    return count;
}

let result = countLeftHeavy(9);
console.log(result);               // 2357