How to implement complete binary in c++?

Question

I want to try make insertion of complete binary tree using recursion . I make a piece of code and I cannot catch problem why value not inserted. I make height function and count nodes function with help of these function and recursive call I want to insert new node in Complete binary tree. In main get root by using get root function then send to insert function

#include<iostream>
#include<math.h>
using namespace std;
struct node{
int data;
node *left,*right;
};
class cbt{
node *root;
    

public:

cbt()
{
root=NULL;

}

node* get_node()
{
return root;
}

       node* newNode(int key)
  {
    node* temp1 = new node;
    temp1->data = key;
    temp1->left = temp1->right = NULL;

    return temp1;
  }


 
 void CBT_inseration(node* temp,int data)
 {
    node *ptr;
    ptr=newNode(data);
    if(root==NULL)
    {
        root=ptr;
        return;
    }
    else
    {
    
    
    
    height = f_height(temp->left);
    int excepted_node = pow(2,height)-1;
    int left_tree_node_count  = countNumNodes(temp->left);
    int right_tree_node_count = countNumNodes(temp->right);

    if(left_tree_node_count==right_tree_node_count)
    {
        CBT_inseration(temp->left,data);
    }
    else if(excepted_node != left_tree_node_count)
    {
        if(temp->left == NULL)
        {
            temp->left = ptr;
            return;
        }else
        {
            CBT_inseration(temp->left,data);
            
        }
    }
    else if(temp->right == NULL)
    {
        temp->right=ptr;
        return;
    }
    else if(excepted_node != left_tree_node_count)
    {
        if(temp->left == NULL)
        {
             temp->left=ptr;
            return;
        }
        else
        {
            CBT_inseration(temp->right,data);
        }
        
    }


    
}
}

void print(node *root) {
    if (root == NULL)
        return;
    print(root->left);
    cout << root->data << " ";
    print(root->right);
}





};
int main()
{
cbt obj;
node *r=NULL;
obj.CBT_inseration(obj.get_node(),4);
obj.CBT_inseration(obj.get_node(),3);
obj.CBT_inseration(obj.get_node(),5);

obj.CBT_inseration(obj.get_node(),8);
obj.print(obj.get_node());
return 0;
  }

Answer 1

You would need to go through a debugger to see what is wrong with your code. I will tell you how I would do this:

First, you need a function to check if the tree is full. We will reuse your functions to do this:

bool isTreeFull(node* head) {
  return head != NULL && countNumNodes(head) == (1 << find_height(head)) - 1;
}

Then for inserting I have to check if the number of nodes on each side are the same. This tells me that I am allowed to move one level deeper on the left side. If the number of nodes aren't the same, then I only move on to insert on the right subtree if the left subtree is full:

void CBT_inseration(int data) {
  root = insert(root, data);
}

node* insert(node* head, int data) {
  if (head == NULL) {
    head = newNode(data);
  } else {
    int leftCount = countNumNodes(head->left);
    int rightCount = countNumNodes(head->right);
    if (leftCount == rightCount) {
      head->left = insert(head->left, data);
    } else {
      if (isTreeFull(head->left)) {
        head->right = insert(head->right, data);
      } else {
        head->left = insert(head->left, data);
      }
    }
  }
  return head;
}

Then you would call it like:

cbt obj;
obj.CBT_inseration(4);
obj.CBT_inseration(3);
obj.CBT_inseration(5);
obj.CBT_inseration(6);
obj.CBT_inseration(8);
obj.print(obj.get_node()); // 6 3 8 4 5