0
$\begingroup$

https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees says

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.[18] An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.[19][20] A complete binary tree can be efficiently represented using an array.[18]

Does that mean

  • a complete binary tree can have at most one node with exactly a child (or can a complete binary tree has at least two nodes with just one child?)

  • in a complete binary tree, a node with exactly a child can only have a left child not a right child.

  • in a complete binary tree, a node with exactly a child can exist only at the level next to the last one, and at that level, all the nodes left to the node must have two children, and all the nodes right to the node must be leaves?

Conversely, do the above three points characterize a complete binary tree?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Using the definition you cite:

  • A complete tree can have at most one node with one child. If there were two such nodes, then the one on the right could shift its child to the left, so the nodes in the last level wouldn't be "as far left as possible".
  • Yes, if a node has only one child, it has to be a left child. Again, because otherwise the child would not be "as far left as possible".
  • Yes, in a complete tree, a node with one child has to be in the second-last level. Its children are partially filled, so its children must be in the last level. Yes all the nodes to its left in the same level must have two children, and all the nodes to its right in the same level are leaves.

Finally, no, these statements do not completely characterize a complete tree. A complete tree might have no nodes at all with only one child, in which case none of these statements about one-child nodes apply to it at all.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Do the three characterize a complete binary tree with (at least) a node with exactly one child? How do you characterize a complete binary tree without such a node? $\endgroup$
    – Tim
    Apr 2, 2022 at 23:21
  • $\begingroup$ They do not. There are other shapes the two-child nodes could make that aren't complete trees. I think your definition has a pretty simple characterization. Another one is that the level-order traversal has no gaps. $\endgroup$
    – Matt Timmermans
    Apr 2, 2022 at 23:23
0
$\begingroup$

No

A complete binary tree has a parent node with two children.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.