C++

Forum

 
Binary Tree Insert Logic Error

Woody1193 (17)
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
template <class T>
  void MyBSTree<T>::insert(const T& x)
  {
    if (m_root == NULL)
    {
      m_root = new treenode<T>;
      m_root->m_data = x;
    }
    else if (x > m_root->m_data)
    {
      if (m_root->m_right == NULL)
      {
        m_root->m_right = new treenode<T>;
        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<T>;
        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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
template <class T>
  struct treenode
  {
    // Variable Declarations
    treenode<T>* m_left;                // Left Child
    treenode<T>* m_right;               // Right Child
    T m_data;                           // Data

    // Member Functions
    treenode(treenode<T>* left = NULL,
             treenode<T>* right = NULL): m_left(left), m_right(right) {};
    treenode(const treenode<T>& cpy)
    {
      m_left = cpy.m_left;
      m_right = cpy.m_right;
      m_data = cpy.m_data;
    }
    MyBSTree<T>* convert()
    {
      return new MyBSTree<T>(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

1
2
3
4
5
 
    9

7

    5


for

1
2
3
 
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
cire (8284)
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
Woody1193 (17)
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
Woody1193 (17)
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.