Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# complete binary tree

Posted on 2006-05-05
Medium Priority
1,287 Views
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?
0
Question by:yattias

LVL 16

Accepted Solution

Peter Kwan earned 128 total points
ID: 16614936
0

LVL 30

Assisted Solution

Mayank S earned 124 total points
ID: 16614941
A complete binary tree has 2 child-nodes for each node (except the leaf nodes).

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.
0

LVL 30

Expert Comment

ID: 16615041
Even this, is not exactly a Java question but a programming TA question ;-)
0

LVL 14

Assisted Solution

hoomanv earned 124 total points
ID: 16615271
A binary tree is a rooted tree in which every node has at most two children.

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/wiki/Binary_tree
0

LVL 12

Assisted Solution

PCableGuy earned 124 total points
ID: 16619160
yattias,

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.
0

LVL 16

Expert Comment

ID: 16848749
i would suggest the splitting of points would be:

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.
0

LVL 30

Expert Comment

ID: 16852909
You probably missed my comment before that comment.
0

LVL 30

Expert Comment

ID: 16852964
Girionis has even given a perfect link to the comment mayankeagle {http:#16614941} which has my first comment (which is not the one where I said that this is the wrong TA) - I suggest you SEE before you directly post a comment like "is pointing out the question is in incorrect TA only, not addressing the question".
0

LVL 16

Expert Comment

ID: 16869137
I am sorry that I missed that link and comment. EE moderator, please ignore my last comment, and include mayankeagle in the point splitting.

mayankeagle, please forgive my carelessness.

Thanks.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
###### Suggested Courses
Course of the Month12 days, 6 hours left to enroll

#### 564 members asked questions and received personalized solutions in the past 7 days.

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