Member Avatar for swissknife007

Can please someone give and explain the algorithm and logic of checking if a given tree is a complete binary tree.
Fields available for a node are left and right child and info.
Thanks.

  • 2 Contributors
  • 1 Reply
  • 522 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

A complete binary tree: every level except possibly the last is full, and nodes on the last level are left‑justified. ’s level‑order → heap‑style array mapping is a good, instructive way to visualise completeness, but it forces allocating an array sized by the tree height (which can be wasteful for tall, sparse trees). The following is a simpler, memory‑friendly BFS method that directly tests completeness in one pass.

Do a normal breadth‑first traversal (queue of actual nodes, not NULLs). Maintain a flag that is set the first time a missing child is seen. For each node popped:

  • if the left child exists and the flag is set, the tree is not complete;
  • if the left child is missing, set the flag;
  • do the same for the right child (right child present after the flag is set -> not complete).

Pseudocode:

function isComplete(root):
    if root == NULL: return true
    q = empty queue
    q.enqueue(root)
    seenMissingChild = false
    while not q.empty():
        node = q.dequeue()
        if node.left != NULL:
            if seenMissingChild: return false
            q.enqueue(node.left)
        else:
            seenMissingChild = true
        if node.right != NULL:
            if seenMissingChild: return false
            q.enqueue(node.right)
        else:
            seenMissingChild = true
    return true

Complexity: O(n) time, O(w) space where w is max width (worst O(n)). Common pitfalls: enqueueing NULL placeholders instead of checking children; forgetting to mark the flag when a left child is missing (a missing left with a later non‑null node makes the tree incomplete); and assuming “full” and “complete” mean the same (they do not). Use this BFS check for a compact, robust implementation; keep ’s heap‑array idea for debugging or visual output.

Member Avatar for Narue

There are multiple ways of doing it, but in my opinion the most instructive is with a level order traversal, since checking for a complete binary tree is a pretty specific operation. By generalizing the problem a bit, you can get more out of the exercise. So here's an updated problem for you:

Q: Given a binary tree of the following definition:

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Write a function that will perform a level order traversal and convert the tree into an array using heap indexing rules. Heap indexing rules state that for each node (numbered 0 to N in level order) the left child is at index 2 * i + 1 and the right child is at 2 * i + 2 .

As an example, given the following degenerate binary tree:

1
        -                      2
   -         -             -        3
 -   -     -   -         -   -    -   4
- - - -   - - - -       - -  - - - - - 5

The array you are to return might look like this:

1-2---3-------4---------------5

Once you have this array, determine if it represents a complete binary tree by testing for null nodes in between non-null nodes. A complete binary tree will have all non-null nodes strictly adjacent to each other. For example, here is a complete binary tree and the array representation:

5
  2         7
1   3     6   -
527136-

Note: The size of the array should be determined as the maximum number of nodes for a tree of height h.

To give you a push in the right direction, you need to figure out how to determine the height of a tree, how to calculate the maximum number of nodes in a tree of given height, and how to perform a level order traversal. Inside the level order traversal you need to maintain the level order index of each node to correctly calculate child indices.

This problem is carefully worded so that you have no choice but to do research on the various techniques, so consult Google before shooting back with questions. I wrote a small program (less than 200 lines) that does all of this. Here are runs on the two examples above:

-
                                5
                                        -
                        4
                                -
                3
                        -
        2
                -
1
        -

*-*---*-------*---------------*
Invalid complete tree
-
        7
                        -
                6
                        -
5
                        -
                3
                        -
        2
                        -
                1
                        -

******-
Complete!

Feel free to match that output if you want. A tree dump with a 90 degree rotation is far easier than the usual textbook representation.

commented: Your effort deserves credit +6
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.