Solved

Posted on 2006-05-05

Can anyone please give me the exact definition of a complete binary tree. How come some sites say that it has to be full up to level h - 1 and some sites have a picture with a binary tree not having the maximum number of elements at h - 1?

9 Comments

A binary tree (which may not be a complete binary tree) need not have 2 child-nodes for each node - some may have just 1 child-node.

A full binary tree is a tree in which every node has zero or two children. Also known as a proper binary tree.

A perfect binary tree is a full binary tree in which all leaves (vertices with zero children) are at the same depth (distance from the root, also called height).

Sometimes the perfect binary tree is called the complete binary tree. Some others define a complete binary tree to be a full binary tree in which all leaves are at depth n or n-1 for some n. In order for a tree to be the latter kind of complete binary tree, all the children on the last level must occupy the leftmost spots consecutively, with no spot left unoccupied in between any two. For example, if two nodes on the bottommost level each occupy a spot with an empty spot between the two of them, but the rest of the children nodes are tightly wedged together with no spots in between, then the whole tree CANNOT be a binary tree due to the empty spot.

An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.

from: http://en.wikipedia.org/wi

I'm feelin your pain. By chance, I'm currently enrolled in a Data Structures and Algorithms class at a college. The comments below paraphrase my instructor's notes on the distinction between a Full Binary Tree and a Complete Binary Tree.

Full Tree - Every node in the tree has 2 child nodes except for the leaf nodes.

Complete Tree - Every level is full, with the possible exception of the level containing the leaf nodes, and the leaf nodes are filled from left-to-right.

The graph in the mathworld link above, from pkwan, agrees with my instructor's definition.

pkwan {http:#16614936} & hoomanv {http:#16615271} & PCableGuy {http:#16619160}

since

mayankeagle is pointing out the question is in incorrect TA only, not addressing the question.

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

zeroMAx challenge | 20 | 65 | |

fetching the full url inside controller | 2 | 31 | |

bunnyEars challenge | 6 | 45 | |

mapShare challenge | 13 | 40 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**15** Experts available now in Live!