about complete binary tree

Question

is this possible that a node in the complete binary tree has just one child? thanks

Can this be a complete binary tree?

        23
       /  \
      12  15
     /  \   
    9   11 
   / \    \
  10  5    13  

Answer 1

OK, first to make the difference between a perfect and a complete binary tree. In a perfect binary tree every node has two children(if not a leaf) or no children(if a leaf). So a perfect binary tree of level N has totally 2^(N + 1) - 1 nodes. But if we talk about complete binary tree - this means every level, except the last is full, and the last level may not be full. Also in a complete binary tree, the last level nodes must be filled from left to right.

So if you talk about perfect binary tree, it is not possible. But if you mean the complete binary tree, it is possible to have only one child.

Answer 2

I would say it is possible:

     *
    / \
   /   \
  *     x
 / \   / 
*   * *

this is a

binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible

And node x has just one child.