### Binary Tree Insert Logic Error

All right, so I was finishing up a BS Tree today and I came across an odd logical error that I cannot figure out. The recursion isn't working and I'm not sure why.

The functions looks as follows
 ``123456789101112131415161718192021222324252627282930`` ``````template void MyBSTree::insert(const T& x) { if (m_root == NULL) { m_root = new treenode; m_root->m_data = x; } else if (x > m_root->m_data) { if (m_root->m_right == NULL) { m_root->m_right = new treenode; m_root->m_right->m_data = x; } else m_root->m_right->convert()->insert(x); } else if (x < m_root->m_data) { if (m_root->m_left == NULL) { m_root->m_left = new treenode; m_root->m_left->m_data = x; } else m_root->m_left->convert()->insert(x); } return; }``````

The implementation I used for this particular tree involved a struct

 ``12345678910111213141516171819202122`` ``````template struct treenode { // Variable Declarations treenode* m_left; // Left Child treenode* m_right; // Right Child T m_data; // Data // Member Functions treenode(treenode* left = NULL, treenode* right = NULL): m_left(left), m_right(right) {}; treenode(const treenode& cpy) { m_left = cpy.m_left; m_right = cpy.m_right; m_data = cpy.m_data; } MyBSTree* convert() { return new MyBSTree(m_data, m_left, m_right); } };``````

and a class MyBSTree which had a single member variable, a point to a treenode<T>.

When I output the tree with T = int, I get

 ``12345`` `````` 9 7 5``````

for

 ``123`` ``````t.insert(7); t.insert(9); t.insert(5);``````

Any number of insertions past this will yield the same output so I know something must be wrong with the insert (or print) function. However, I think it is my insert function because the print function is too simple for a bug like this to occur. Furthermore, if it was the print function, only the deepest degree of the tree wouldn't print. Thus, the insert function.

Anyone have suggestions?
Last edited on
Erm.. You insert the new elements into a completely unconnected tree created by convert (also causing a memory leak in the process.) And by unconnected I mean there is nothing in the original tree connecting it to the tree created by convert.
Last edited on
I see. The problem, though, is that most of the work is done through a treenode but the calling object for the function is a MyBSTree. So I'm at a loss for how I would make this function work.
Last edited on
I had to create a second insert function for the treenode<T> class. It annoys me that I had to resort to a solution like that but it works anyway.
Topic archived. No new replies allowed.