CODEWITHSUNDEEP
cbinary-search-tree
user1010101
user1010101

Reputation: 1658

Binary Tree - Complete

I am currently learning about the BST and writing different functions such as insert search. I came across an interesting programming interview question and it asked to write a function that will check if the bst is complete.

So my understanding is that a BST is complete if all the leaves terminate at the same level.

My possible approach for this solution

I figured that height of the right and left nodes should be the same if the leaves under them terminate at the same level. so can I do a simple check to see if the height of a right sub tree is the same as the left sub-tree and if it is then that should indicate to me that the BST tree is complete. Can anyone confirm if my approach is right or suggest other possible approaches? i am not looking for code just want to work on my understanding and approach.

Upvotes: 0

Views: 214

Answers (3)

Michael Laszlo
Michael Laszlo

Reputation: 12239

Your recursive approach is almost correct. What you want to ask about a given node are the following questions:

  • Is the left child the root of a complete BST, and if so, what is its height?
  • Is the right child the root of a complete BST, and if so, is its height the same as that of the left child?

If the answer to both is yes, you have a complete BST.

A different way to solve this problem is to answer the following three questions about the tree.

  • Is it a BST?
  • How many nodes are in it?
  • What is its height?

If the tree is a BST of height h with 2**h - 1 nodes, you have a complete BST. Each of the three questions can be answered with a recursive tree traversal.

Upvotes: 2

Min Fu
Min Fu

Reputation: 809

Your basic idea I think is correct. You just recursively check whether the left tree is of the same height as the right tree.

The code looks like

int isComplete(Tree *t){
    if(t->left==NULL && t->right==NULL)
        return 0;
    else if(t->left!=NULL && t->right != NULL){   
        int leftheight = isComplete(t->left);
        int rightheight = isComplete(t->right);
        if(leftheight == rightheight && leftheight != -1)
            return leftheight+1；
    }
    return -1;
}

-1 indicates not complete. A non-negative return indicates the height of the tree.

Upvotes: 1

nomier
nomier

Reputation: 412

Your approach won't work because the tree might be equal on left and right and not the same for all leaves like:

      5
      /\
     3  6
    /   \
   1     7

This tree has equal left and right but 6 doesn't have left child and 3 doesn't have right child. And the definition of complete tree is 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

Number of nodes = 2^n-1 is not going to solve it as well because it might contain that number but not balanced.

The correct approach would be to

  • traverse the tree using something like post-order traversal and when you reach the first leaf, you set the max_depth
  • during the traversal if you reach a leaf node, it must be at max_depth or depth can decrease to be max_depth -1 but the depth can't increase again after that.

and that is to handle a case like this (which is a complete BST tree)

      4
      /\
     2  6
    / \  /\
   1   3 5

Upvotes: 1

Related Questions