CODEWITHSUNDEEP
javabinary-tree
Jigglypuff
Jigglypuff

Reputation: 1463

How to check if a binary tree is complete in Java

I am having a lot of trouble with this task. Using the Wikipedia definition for a complete binary tree:

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

I need a way of checking for these conditions, but no matter how much I try, I can't seem to come up with anything. If I were to pass a TreeNode tree input into a checkComplete method how could I go about going through the binary tree and checking that it is complete? Can anyone help with pseudocode or an explanation of how this is possible? There was another question here: How to determine whether a binary tree is complete?

This one had an answer with pseudocode in it, but I couldn't understand where all the random variables were coming from or what they were meant to represent or why there were two values in brackets in the last 3 lines. If anyone could help with another representation I'd really appreciate it.

Upvotes: 1

Views: 5264

Answers (2)

Neha
Neha

Reputation: 37

int CT()
{
  int lh=0, rh=0, sign=1;
  if (!root->left && !root->right) 
    return 1;
  if (!root->left && root->right) 
    return 0;

  lh = CT(root->left);
  rh = CT(root->right);

  if (lh == 0 || rh == 0) 
    return 0;
  if (lh < 0 && rh < 0) 
    return 0;
  if (lh < 0 || rh < 0) 
    sign = -1;
  if (|lh| == |rh| ) 
    return (|lh|+1)*sign;
  elseif (rh == lh-1) 
    return -(|lh|+1);
  else return 0;
}

if CT returns '0' - its not a complete tree.
'-' is used to check mismatch in height is encountered on one subtree only.

Upvotes: 2

Andy Thomas
Andy Thomas

Reputation: 86509

Traverse the tree left-to-right. There are several critical points at which you'll want to store or compare information:

  • When you hit the first leaf node.
  • When you hit subsequent leaf nodes.
  • When you hit the first leaf node with a different distance from the root.

Since this is homework, you should probably take it the rest of the way from that hint.

Upvotes: 1

Related Questions