# Attempting to get this interative binary tree insert to work.

• Eruditee
In summary: temp->left=temp->right; temp->right=0; } else if (item<this->root->data){ nodep temp = this->root->left; while (temp!=0){ if(temp->data<item) temp=temp->left; else if (temp->data>item)
Eruditee

## Homework Statement

Binary Tree/ Insertion scheme

N/A

## The Attempt at a Solution

Code:
bool treeNodeADT::_insert(int item) {
if(this->isRootted==false){
this->root=new node;
this->root->data=item;
this->root->right=0;
this->root->left=0;
this->isRootted = true;
}
else if (item>this->root->data){
nodep temp = this->root->right;
while (temp!=0){
if(temp->data>item)
temp=temp->left;
else if (temp->data<item)
temp = temp->right;
else return false;
}
temp = new node;
temp->data=item;
temp->left=0;
temp->right=0;
}
else if (item<this->root->data){
nodep temp = this->root->left;
while (temp!=0){
if(temp->data>item)
temp=temp->left;
else if (temp->data<item)
temp = temp->right;
else return false;
}
temp = new node;
temp->data=item;
temp->left=0;
temp->right=0;
}

}

In short, there's a static variable in which isRotted (mispelled) shows whether the root has been constructed. I then follows the root in either its left or right directions by the if/esls shceme. Then when it gets to a point in which the data shows contrast, it decides to move left or right until a blank node has been found.

I never get into the whiles. Help? I can do this iteratively, but after I found out that's more computationally expensive, I want to learn this way in the event I need to use it for time sensitive cases.

Eruditee said:

## Homework Statement

Binary Tree/ Insertion scheme

N/A

## The Attempt at a Solution

Code:
bool treeNodeADT::_insert(int item) {
if(this->isRootted==false){
this->root=new node;
this->root->data=item;
this->root->right=0;
this->root->left=0;
this->isRootted = true;
}
else if (item>this->root->data){
nodep temp = this->root->right;
while (temp!=0){
if(temp->data>item)
temp=temp->left;
else if (temp->data<item)
temp = temp->right;
else return false;
}
temp = new node;
temp->data=item;
temp->left=0;
temp->right=0;
}
else if (item<this->root->data){
nodep temp = this->root->left;
while (temp!=0){
if(temp->data>item)
temp=temp->left;
else if (temp->data<item)
temp = temp->right;
else return false;
}
temp = new node;
temp->data=item;
temp->left=0;
temp->right=0;
}}
In short, there's a static variable in which isRotted (mispelled) shows whether the root has been constructed. I then follows the root in either its left or right directions by the if/esls shceme. Then when it gets to a point in which the data shows contrast, it decides to move left or right until a blank node has been found.

I never get into the whiles. Help? I can do this iteratively, but after I found out that's more computationally expensive, I want to learn this way in the event I need to use it for time sensitive cases.

It seems flaky to me that you are setting what appear to be pointer variables with the integer value 0.

A major problem that I see is that if the node is not rooted, a new node is created, with its data, left, and right fields set, and then the function exits without returning a boolean value. The way you have your code indented makes it a little harder to notice that in certain cases your function doesn't return a value.

The proper indentation would look similar to this:
Code:
bool treeNodeADT::_insert(int item) {
if(this->isRootted==false){
// body of if clause
}
else if (item>this->root->data){
// body of else if clause
}
else if (item<this->root->data){
// body of else if clause
}
}

Also, what happens if item == this->root->data? You don't have any logic to handle that case.

Some of your code is more difficult to follow than it should be; for example, item>this->root->data

Add some spaces to increase readability, especially for the inequality operators. Without extra spacing it's harder to distinguish them from the struct pointer dereference operators.

Finally, if you are working with pointers, and aren't using a debugger to single-step through your code and inspect the values of variables, start learning to use one right away. You didn't mention what compiler you're using, but I'm pretty sure that there is some debugger available in whatever system you're using.

BTW, "IsRootted" and "IsRotted" are both misspellings. What you should have is "IsRooted".

Mark44 said:
It seems flaky to me that you are setting what appear to be pointer variables with the integer value 0.

A major problem that I see is that if the node is not rooted, a new node is created, with its data, left, and right fields set, and then the function exits without returning a boolean value. The way you have your code indented makes it a little harder to notice that in certain cases your function doesn't return a value.

The proper indentation would look similar to this:
Code:
bool treeNodeADT::_insert(int item) {
if(this->isRootted==false){
// body of if clause
}
else if (item>this->root->data){
// body of else if clause
}
else if (item<this->root->data){
// body of else if clause
}
}

Also, what happens if item == this->root->data? You don't have any logic to handle that case.

Some of your code is more difficult to follow than it should be; for example, item>this->root->data

Add some spaces to increase readability, especially for the inequality operators. Without extra spacing it's harder to distinguish them from the struct pointer dereference operators.

Finally, if you are working with pointers, and aren't using a debugger to single-step through your code and inspect the values of variables, start learning to use one right away. You didn't mention what compiler you're using, but I'm pretty sure that there is some debugger available in whatever system you're using.

BTW, "IsRootted" and "IsRotted" are both misspellings. What you should have is "IsRooted".
Yes, isRooted. I'm in NetBeans, which uses gdb. The indentation is actually auto-formatted in NetBeans itself? It doesn't add spacing with operators. I should, however.

I'm using 0 to avoid preprocessor time. Apparently, NULL is just a C++ macro or #define NULL 0

This works:
Code:
bool TreeADT::_insert(int item, nodep& a) {
if (a == 0) {
a = new node;
a->data = item;
a->left = 0;
a->right = 0;
return true;
}
else if (a->data > item)
_insert(item, a->left);

else if (a->data < item)
_insert(item, a->right);

else
return false;
}

This is how I understand it best because it's just sequential on a stack, then popped off etc. Also, it's easier to see a stack trace for this and follow it.

This does not work:
Code:
bool TreeADT::_insert(int item, nodep a) {
if (a == 0) {
a = new node;
a->data = item;
a->left = 0;
a->right = 0;
return true;
}
else if (a->data > item)
_insert(item, a->left);

else if (a->data < item)
_insert(item, a->right);

else
return false;
}

I think it's because in the while version, I am passing root by value. Uninitialized, it does nothing but most likely give it a null pointer, as root is null to begin with.

It's easier to circumvent this in the recursive version becaue each time it runs, it is instructed to work on the actual entity as opposed to a copy somewhere else in the heap.

I'm not sure how to really do these iteratively. It was just to test it out because I figured iterative processes would be much faster, but I don't think big trees are used in microprocessing or in places where memory is sparse?

This isn't homework. It's just a self-practice; I posted it here as it seemed the most appropos. As to style, I'm learning Python and will most likely use that indentation style in all of my programming, as it just nicely enforces very readable style to even compile.

Thankx

## What is an interactive binary tree?

An interactive binary tree is a data structure that organizes data in a hierarchical manner, where each node has at most two child nodes. It allows for efficient searching, insertion, and deletion of data.

## What is a binary tree insert?

A binary tree insert is the process of adding a new node to an existing binary tree. This involves finding the correct location for the new node based on its key value and inserting it into the tree while maintaining the binary tree properties.

## Why is the insert method not working?

There could be several reasons why the insert method is not working. Some common reasons include errors in the code, incorrect implementation of the algorithm, or issues with the input data. It is important to carefully review the code and troubleshoot to identify the specific issue.

## What are the steps involved in inserting a node into a binary tree?

The steps involved in inserting a node into a binary tree are:

1. Compare the key value of the new node with the key value of the root node.
2. If the new node's key value is smaller, go to the left child node. If it is larger, go to the right child node.
3. Repeat step 2 until reaching a null child node.
4. Insert the new node at the null child node.

## How can I test if my binary tree insert is working correctly?

One way to test if the binary tree insert is working correctly is to manually insert nodes and then traverse the tree to ensure that all the nodes are in the correct place. Another way is to create various test cases with different input data and compare the expected output with the actual output of the insert method.

• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
14
Views
4K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
2
Views
3K
• Programming and Computer Science
Replies
12
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
4
Views
2K