about complete binary tree

Question

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

EDIT : this can 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

Citing Wikipedia:

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

Which means no.

Answer 3

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.

Answer 4

From the other answers:

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

        23
       /  \
      12  15
     /  \   
    9   11     <- not the last level, but not completely filled!
   / \    \
  10  5    13  <- last level: not completely filled, but that's okay

So this example tree is not complete, according to this definition.