I've been trying to solve this problem as a practice:
The complete binary tree has V = {a, b, c, e, f, g, h, i, j, k}. The postorder listing of V yields {d, e, b, h, i, f, j, k, g, c, a}. From this information draw T if:
a) the height of T is 3
b) the height of the left subtree of T is 3
Now for a, I drew this, which I think is correct.
For b, I'm confused. I'm not sure how this is possible. I checked the solution and saw this:
How is this correct? Shouldn't complete binary trees be full at height-1? I'm not even sure if it's possible to draw this tree. Can anyone help?
The solution to your confusion is simple: both solutions are correct. Indeed, neither pre-, in- or post-order describes the underlying tree uniquely. Even if you have pre-order and post-order, it does not suffice to describe the tree. However, having pre- and in-order (or post- and in-order) suffices to describe the tree. See Tree traversal for more details.
EDIT. As Henning Makholm pointed out, the OP's answer is correct if you restrict to complete binary tree in Knuth's sense. Just be aware that this definition is not fully accepted. For instance, Cormen, Leiserson, Rivest and Stein use a more restricted definition (all leaves have the same depth), which would not make sense in the context of this question. But I have also seen a "middle term" definition: all leaves have depth $n$ or $n-1$ for some $n$. With this definition, several solutions are again possible.