# Data structure job - determine whether the binary tree is complete

## What is a complete binary tree

Complete binary tree

## Method 1

Depth first search, first search the left subtree, then the right subtree. When the traversing node is a leaf node, the depth of the leaf node is stored in the array, and finally judge whether the number is like a shape Or like If so, then this tree is a complete binary tree, otherwise, it is not a complete binary tree. Take the following tree as an example. The code is as follows: ```#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
node* left;
node* right;
}*tree, *root;
int deep, cnt;
//Initialize tree building
void Init()
{
for (int i = 0; i < 1005; i++)
{
tree[i] = (node*)malloc(sizeof(node));
tree[i]->left = NULL;
tree[i]->right = NULL;
}
root = (node*)malloc(sizeof(node));
root = tree;
root->left = tree;
root->right = tree;
tree->left = tree;
tree->right = tree;
tree->left = tree;
tree->right = tree;
tree->left = tree;
tree->right = tree;
tree->left = tree;
}
//Depth first search for leaves
void Dfs(node* root, int dep)
{
if (root->left == NULL && root->right == NULL)
{
deep[cnt++] = dep;
return;
}
if (root->left != NULL)
Dfs(root->left, dep + 1);
if (root->right != NULL)
Dfs(root->right, dep + 1);
}
//Output deep array
void Print()
{
for (int i = 0; i < cnt; i++)
printf("%d%c", deep[i], i == cnt - 1 ? '\n' : ' ');
}
//Determine whether the binary tree is complete
bool Check()
{
int f = 0;
for (int i = 1; i < cnt; i++)
{
if (deep[i - 1] != deep[i])
{
if (deep[i - 1] == deep[i] + 1)
f++;
else
return false;
}
}
if (f <= 1)
return true;
return false;
}
int main()
{
Init();
Dfs(root, 1);
Print();
puts(Check() ? "Yes" : "No");
}```

## Method 2:

Breadth first search, layer by layer search. When the traversed node is a leaf node, the depth of the leaf node is stored in the array, and finally the number is judged to be the shape Or like If so, then this tree is a complete binary tree, otherwise, it is not a complete binary tree.

Take the tree above as an example and the code is as follows:

```#include <bits/stdc++.h>
#define Pair pair<node*,int>
#define ll long long
using namespace std;
struct node
{
node* left;
node* right;
}*tree, *root;
int deep, cnt;
//Initialize tree building
void Init()
{
for (int i = 0; i < 1005; i++)
{
tree[i] = (node*)malloc(sizeof(node));
tree[i]->left = NULL;
tree[i]->right = NULL;
}
root = (node*)malloc(sizeof(node));
root = tree;
root->left = tree;
root->right = tree;
tree->left = tree;
tree->right = tree;
tree->left = tree;
tree->right = tree;
tree->left = tree;
tree->right = tree;
tree->left = tree;
}
//Depth first search for leaves
void Bfs(node* root)
{
queue<Pair>q;
q.push(Pair{ root,1 });
while (!q.empty())
{
Pair temp = q.front();
q.pop();
if (temp.first->left == NULL && temp.first->right == NULL)
deep[cnt++] = temp.second;
if (temp.first->left != NULL)
q.push(Pair{ temp.first->left ,temp.second + 1 });
if (temp.first->right != NULL)
q.push(Pair{ temp.first->right ,temp.second + 1 });
}
}
//Output deep array
void Print()
{
for (int i = 0; i < cnt; i++)
printf("%d%c", deep[i], i == cnt - 1 ? '\n' : ' ');
}
//Determine whether the binary tree is complete
bool Check()
{
int f = 0;
for (int i = 1; i < cnt; i++)
{
if (deep[i - 1] != deep[i])
{
if (deep[i - 1] + 1 == deep[i])
f++;
else
return false;
}
}
if (f <= 1)
return true;
return false;
}
int main()
{
Init();
Bfs(root);
Print();
puts(Check() ? "Yes" : "No");
}```

Added by MysticalCodex on Sun, 03 Nov 2019 07:01:12 +0200