CODEWITHSUNDEEP
c++binary-tree
Don Code
Don Code

Reputation: 878

Generating a balanced binary tree

I am not sure if this is doing what it is supposed to do. My goal is to generate a balanced binary tree, from a set of values. Please let me know if this is correct.

NOTE: NOT a balanced binary search tree, just balanced binary tree.

int heightPrivate(nodePtr node)
{
if (node == NULL)
  return -1;

return 1 + std::max(heightPrivate(node->left), heightPrivate(node->right));
} 

void addNodePrivate(nodePtr node, int val)
{
  if (root == NULL)
  {
    root = new BTNode;
    root->data = val;
    root->left = root->right = NULL;
  }
  else
  {
    if (node->left == NULL)
    {
      node->left = new BTNode;
      node->left->data = val;
      node->left->left = node->left->right = NULL;
    }
    else if (node->right == NULL)
    {
      node->right = new BTNode;
      node->right->data = val;
      node->right->left = node->right->right = NULL;
    }
    else
    {
      int lheight = heightPrivate(node->left);
      int rheight = heightPrivate(node->right);

      if (lheight < rheight)
        addNodePrivate(node->left, val);
      else if (rheight < lheight)
        addNodePrivate(node->right, val);
      else
        addNodePrivate(node->left, val);
    }
  }
}

void printPostorderPrivate(nodePtr p, int indent=0)
{
  if(p != NULL) {
    if(p->left) printPostorderPrivate(p->left, indent+4);
    if(p->right) printPostorderPrivate(p->right, indent+4);
    if (indent) {
        std::cout << std::setw(indent) << ' ';
    }
    std::cout<< p->data << " \n ";
  }
}

In main...

int main()
{
  BTree tree;

  tree.addNode(1);
  tree.addNode(2);
  tree.addNode(3);
  tree.addNode(4);
  tree.addNode(5);
  tree.addNode(6);
  tree.addNode(7);

  tree.printPostorder();

The result I get is this:

            7
         4 
         6
     2
         5
     3
 1

The children of 2 are 4 and 5. The question is why is it 7 going on the next level.

Upvotes: 0

Views: 504

Answers (1)

Ario Aliabadi
Ario Aliabadi

Reputation: 90

The reason that 7 appears where it does is because in the addNodePrivate method checks the heights of the two child branches, and if they are equal it goes left.

So as you insert 7, when the program is at the root (node 1) it sees that the height of the left branch and height of the right branch are both equal to 1 (node 2 had children 5 and 4 but no grandchildren, and node 3 has child 6 and also no grandchildren), and so it goes left - down the branch with node 2.

To achieve what you want, you need to choose the branch which has the shortest path, so comparing the height of two branches is not enough.

Hope that helps, best of luck.

Upvotes: 2

Related Questions