Public Group

# BinaryTree Question

This topic is 2920 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Is it possible to add nodes into a binary tree in order of increasing value, level by level?
For example:
1
2  3
4 56 7

Yes.

##### Share on other sites
I am using a basic binary tree and am adding node values in order 1,2,3... I can get the first 3 values in the right place but the rest just keep adding to the left sub trees.

void Insert(Node *&nodePtr, Node *&newNode)
if(nodePtr == NULL)
nodePtr = newNode;
else
{
if(nodePtr->left == NULL)
Insert(nodePtr->left,newNode);
else
if(nodePtr->right == NULL)
Insert(nodePtr->right,newNode);
else
Insert(nodePtr->left,newNode);
}

I also tried using parent nodes but that is getting to complicated to follow. Is there a better solution using a binary tree?

void Insert(Node *&nodePtr, Node *&newNode, Node *&parentNode)
{
if(nodePtr == NULL)
{
nodePtr = newNode;
nodePtr->parent = parentNode;
}
else
{
if(nodePtr->left == NULL)
Insert(nodePtr->left,newNode,nodePtr);
else
if(nodePtr->right == NULL)
Insert(nodePtr->right,newNode,nodePtr);
else
Insert(nodePtr->left,newNode,nodePtr);
}

##### Share on other sites
There is quite some theory behind it. This type of tree is called a heap. This alone is not enough.

To get items sorted by level one needs to sort a heap - aka Heap Sort.

The only complication is that heap sort prefers to work on arrays. To implement those over this type of nodes, the tree traversal needs to be adjusted. The following are equivalent:
node:   index
node->parent: index/2
node->left: 2*index
node->right: 2*index+1

The simplest way is to build any binary tree ignoring the order. Then apply heap sort.

##### Share on other sites
One of the interesting properties of a binary tree filled with consecutive numbers like that is that the binary representation of the values tell you how to get to the node that contains the value. Take the number 4; it's binary representation is 100. It likes on the third level because it's most significant bit is in the third position. In order to get to its node you take two left paths because the representation is 00. The number 5's representation is 101. It too is on the third level and to get to it's node you go left then right. 0 for the left and 1 for the right. The number 6's representation is 110. To get to it you go right then left. 7 is 111 so you go right twice.

##### Share on other sites
Well, for strictly consecutive it's also possible to be a bit clever:

Node * add(int curr, int max) {
if (curr > max) return NULL;
Node * n = new Node();
n->value = curr;
return n;
};

Node * root = add(1, 7);

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
14
5. 5

• 14
• 10
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632630
• Total Posts
3007526
• ### Who's Online (See full list)

There are no registered users currently online

×