C++

Forum

 
binary tree questions

Pages: 12
jamesfarrow (211)
Hello everyone - have a question about traversing a binary tree to insert a node correctly. Struggling at the mo :(

This is what Have so far

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 

#ifndef tree_hpp
#define tree_hpp

#include <iostream>
//left is less than
//right is greater than

template<typename T>
class tree
{
    struct node
    {
        node* m_left;
        node* m_right;
        T m_val;
        
        node(T val, node* left=nullptr, node* right=nullptr)
        : m_val(val), m_left(left), m_right(right) {}
       
    };
private:
    //node* root{nullptr};
public:
    node* root{nullptr};
    
    void insert(T v)
    {
        if(!root)
        {
            node* newroot = new node(v);
            root = newroot;
        }
        else
        {
            node* newnode = new node(v);
            node* temp{root};
            //how to succesfully traverse tree going left/right until correct pos found??
            while(1)//what to do here?
            {
                if(newnode->m_val < temp->m_val)
                {
                    //what to do here??
                }
                else
                {
                    //what to do here??
                }
            }
        }
    }
            
            
            
            
    bool contains(T v)
    {
        return false;
    }
};

#endif /* tree_hpp */
jonnin (11438)
node* newroot = new node(v);
root = newroot;

redundant.. don't need excess variable and copy, just say
root = new node(v);

this isnt wrong, its just silly.

-----------
tree traversals work best with recursion.
in pseudo code ..
void insert(node *&root, nodedata)
{
if(!root) node = new node(nodedata);
else if(nodedata < root.data)
insert(root.left, nodedata)
else insert(root.right, nodedata)
}

its doable without the recursion, perhaps:
temp ** = &root; //add a layer so in the loop you don't get a copy of null

do
if(!(*temp))
{
*temp = new node(data);
done = true;
}
else if (data < *temp.data) temp = &temp.left;
else temp = &temp.right;
while(!done)

do you understand the second layer? If you just say temp = new node, and temp was null, that just assigns a null pointer to a new node, but how is THAT connected to the tree? It isnt!
The extra layer puts it back into the previous node's pointer, via addressing, (assuming I didn't screw it up) and thus its IN the tree. With the recursion, the call stack is doing this for you.

Someone let him know if this is way off base. I am feeling a little more foggy than usual :(
Last edited on
zapshe (1907)
As jonnin said, recursion is the easiest way to to this.

Anyway, here's a simple way which you would need to modify to know whether to traverse from left or right with the binary tree:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
template<typename T>
class tree
{
	struct node
	{
		node* m_left;
		node* m_right;
		T m_val;

		void insert(T v)
		{
			if (m_left == nullptr)
			{
				m_left = new node(v);
			}
			else if (m_right == nullptr)
			{
				m_right = new node(v);
			}

			else if (...)//Condition to know whether to go Left or Right
			{
				m_left->insert();
			}
			else
			{
				m_right->insert();
			}
		}

		node(T val, node* left = nullptr, node* right = nullptr)
			: m_val(val), m_left(left), m_right(right) {}

	};
public:
	node* root{ nullptr };

	void insert(T v)
	{
		if (root == nullptr)
		{
			root = new node(v);
		}
		else
		{
			root.insert(v);
		}
	}

	bool contains(T v)
	{
		return false;
	}
};
jamesfarrow (211)
Thanks for your help and advice on how to do this. I have taken on board what has been said and with changes I have managed to get insert() working. I also thought if it 'works' for insert() then it will work for contains() as well.

I have not tested exhaustively yet but with what I have done all is ok

Thanks again!

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 

#ifndef tree_hpp
#define tree_hpp

#include <iostream>
//left is less than
//right is greater than

template<typename T>
class tree
{
    struct node
    {
        node* m_left;
        node* m_right;
        T m_val;
        
        //insert value into tree
        void struct_insert(T v)
        {
            if (v < m_val)//is val less than current node
            {
                if (m_left == nullptr)//is next node null then insert here
                {
                    m_left = new node(v);//insert
                }
                else m_left->struct_insert(v);//continue further into tree
            }
            else
            {
                if(m_right == nullptr)//is next node null then insert here
                {
                    m_right = new node(v);//insert
                }
                else m_right->struct_insert(v);//continue further into tree
            }
           
        }
        //function to search for specific value
        bool struct_contains(T v)
        {
            if(v == m_val)return true;//if there return found
            else if(v < m_val)//is key lower than current node value
            {
                if(m_left == nullptr) return false;//is next node null then key is not in tree
                else return m_left->struct_contains(v);//go further into tree and continue with search
            }
            else
            {
                if(m_right == nullptr) return false;//is next node null then key is not in tree
                return m_right->struct_contains(v);//go further into tree and continue with search
            }
            
        }
        //node constructor
        node(T val, node* left=nullptr, node* right=nullptr)
        : m_val(val), m_left(left), m_right(right) {}
       
    };
private:
    node* root{nullptr};
public:
    //node* root{nullptr};
    
    void insert(T v)
    {
        if(!root)
        {
            root = new node(v);
        }
        else
        {
            root->struct_insert(v);
        }
    }
            
    bool contains(T v)
    {
        return root->struct_contains(v);
    }
};

#endif /* tree_hpp */
jamesfarrow (211)
In insert() maybe the first statement should be
if(v == m_val) return;

This way if a duplicate is added to the tree it will simply return?
Is this a good way to handle duplicate entries?
zapshe (1907)
Yea. As you go through the binary tree with struct_insert(), you can simply compare the value with the values contained in each node along the way. Since the binary tree has a logical flow in how you insert things, you should always pass through the node containing the same value if it exists.
jonnin (11438)
you have to look to your requirement on how to handle duplicates.
3 ways come to mind right away..
1) ignore them (do not allow, this is what you suggest)
2) insert them (it works fine, a few of your statements become <= or the default else will handle them with implied <=) (this could be >= as well, either direction you like). so like in my example
else if(nodedata < root.data)
insert(root.left, nodedata)
else insert(root.right, nodedata) <---- this will also get the equal ones, via the else throwing them down here

3) you can add a counter to your node type and increment it for duplicates, decrement it when you delete one copy of the duplicate. This can also assist with a lazy delete strategy where instead of deleting, you leave it there and mark it dead (here, count == 0 is none left). Once in a while you can build a new tree from the old one and toss out the zero ones to reduce its size to keep it running efficiently.
Last edited on
jamesfarrow (211)
Thanks again, for the time being I am going with option 1) ignore them. If it arises later then I can deal with it!
Next problem is a destructor().
I have come up with this
In struct node I have created the following

1
2
3
4
5
6
7
8
9
 

//node destructor
        ~node()
        {
            delete m_left;
            delete m_right;
            std::cout << "deleting " << this->m_val << std::endl;
        }



Then in tree class I have, so far it appears to do delete everything
1
2
3
4
5
6
7
 

~tree()
    {
        std::cout << "tree destructor" << std::endl;
        delete root;
    }

jonnin (11438)
that leaks memory.
you have to destroy same way you traverse, all the way to the leaves, delete, then back up and delete root last.
its good idea to set deleted pointers null after calling delete. this prevents using a deleted pointer accidentally.

do you need a routine that deletes one node and rebuilds the tree around that?
Last edited on
zapshe (1907)
I've tested it and it doesn't leak as far as this code goes:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
#include <iostream>
#include <random>

template<typename T>
class tree
{
public:
	//tree() {}
	~tree()
	{
		std::cout << "tree destructor" << std::endl;
		delete root;
	}
private:
	struct node
	{
		node* m_left;
		node* m_right;
		T m_val;

		//insert value into tree
		void struct_insert(T v)
		{
			if (v < m_val)//is val less than current node
			{
				if (m_left == nullptr)//is next node null then insert here
				{
					m_left = new node(v);//insert
				}
				else m_left->struct_insert(v);//continue further into tree
			}
			else
			{
				if (m_right == nullptr)//is next node null then insert here
				{
					m_right = new node(v);//insert
				}
				else m_right->struct_insert(v);//continue further into tree
			}

		}
		//function to search for specific value
		bool struct_contains(T v)
		{
			if (v == m_val)return true;//if there return found
			else if (v < m_val)//is key lower than current node value
			{
				if (m_left == nullptr) return false;//is next node null then key is not in tree
				else return m_left->struct_contains(v);//go further into tree and continue with search
			}
			else
			{
				if (m_right == nullptr) return false;//is next node null then key is not in tree
				return m_right->struct_contains(v);//go further into tree and continue with search
			}

		}
		//node constructor
		node(T val, node* left = nullptr, node* right = nullptr)
			: m_val(val), m_left(left), m_right(right) {}

		~node()
		{
			delete m_left;
			delete m_right;
			std::cout << "deleting " << this->m_val << std::endl;
		}

	};
private:
	node* root{ nullptr };
public:
	//node* root{nullptr};

	void insert(T v)
	{
		if (!root)
		{
			root = new node(v);
		}
		else
		{
			root->struct_insert(v);
		}
	}

	bool contains(T v)
	{
		return root->struct_contains(v);
	}
};


int main()
{
	tree<int> apple;
	std::random_device rd;
	std::mt19937 mersenne(rd());
	std::uniform_int_distribution<> q(1, 100);
	for(int i = 0; i < 100; i++)
		apple.insert(q(mersenne));
}



that leaks memory

I thought it would as well, but apparently delete becomes recursive behind the scenes, calling the destructor for each object before freeing the memory:

https://stackoverflow.com/questions/34170164/destructor-for-binary-search-tree

It's been a while since I've dealt with new and delete, let alone binary trees.
jonnin (11438)
hmm, ok.
if it works, it works... leave it be :)
dhayden (5798)
You can really simplify the code by creating a single function that returns a reference to the pointer in the tree where the node is, or where it should go. This is a little hard to follow because it uses a pointer-to-pointer (pp) that points to root, or the pointer to the current node (i.e. the left or right pointer of the parent)
1
2
3
4
5
6
7
8
9
10
 
    node * &location(const T& v)
    {
	node *p, **pp;
	for (pp = &root; (p = *pp);) {
	    if (v < p->m_val) pp = &p->m_left;
	    else if (v > p->m_val) pp = &p->m_right;
	    else break;		// they are equal
	}
	return *pp;
    }


Once you have this, insert() and contains() are trivial:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include <iostream>
#include <random>

template < typename T > class tree {
  public:
    //tree() {}
    ~tree() {
	std::cout << "tree destructor" << std::endl;
	delete root;
    }
  private:
    struct node
    {
	T m_val;
	node *m_left;
	node *m_right;
	node (T val) : m_val(val), m_left(nullptr), m_right(nullptr) {}

	~node() {
	    delete m_left;
	    delete m_right;
	    std::cout << "deleting " << this->m_val << std::endl;
	}
	void print(std::ostream &os) {
	    if (m_left) m_left->print(os);
	    os << m_val << ' ';
	    if (m_right) m_right->print(os);
	}
	
    };

    node * &location(const T& v)
    {
	node *p, **pp;
	for (pp = &root; (p = *pp);) {
	    if (v < p->m_val) pp = &p->m_left;
	    else if (v > p->m_val) pp = &p->m_right;
	    else break;		// they are equal
	}
	return *pp;
    }
		
private:
    node * root { nullptr};

public:

    //insert value into tree. Return true on success, false if v is already
    // in the tree
    bool insert(T v)
    {
	node * &loc(location(v));
	if (loc) return false;
	loc = new node(v);
	return true;
    }

    //function to search for specific value
    bool contains(T v)
    {
	return location(v) != nullptr;
    }

    void print(std::ostream &os) {
	if (root) root->print(os);
	else os << "empty\n";
    }
};

int
main()
{
    tree < int >apple;
    std::random_device rd;
    std::mt19937 mersenne(rd());
    std::uniform_int_distribution <> q(1, 100);
    for (int i = 0; i < 100; i++)
	apple.insert(q(mersenne));
    apple.print(std::cout);
    
}

jamesfarrow (211)
Sorry for late reply! I have been trying to get remove() function to work on my tree. I can't get anything to work. I have been on with for a while now.
I am thinking a complete re-write maybe the only option :(

jamesfarrow (211)
dhayden I have not come across **p in my efforts with c++ yet. I have 'messed around' with C++ for a year or so but only recently decided to have a decent crack at learning it and becoming proficient with it.
I am very much on the first few steps of the journey!!
That being said I am willing to go and find answers when pointed in right right direction!

Thanks again for taking the time to help.
zapshe (1907)
The reason it'll be harder to implement a remove() is because of your node destructor which makes delete recursive. If you try to delete a single object, it goes on an deletes everything it points to and so on.

You only have to change the ~Node (destructor). Instead, you can have a separate function that can delete the entire tree:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
#include <iostream>
#include <random>

template<typename T>
class tree
{
	struct node
	{
		node* m_left;
		node* m_right;
		T m_val;

		//insert value into tree
		void struct_insert(T v)
		{
			if (v < m_val)//is val less than current node
			{
				if (m_left == nullptr)//is next node null then insert here
				{
					m_left = new node(v);//insert
				}
				else m_left->struct_insert(v);//continue further into tree
			}
			else
			{
				if (m_right == nullptr)//is next node null then insert here
				{
					m_right = new node(v);//insert
				}
				else m_right->struct_insert(v);//continue further into tree
			}
		}

		void remove(T v)
		{
			if (v < m_val)
			{
				if (m_left != nullptr && m_left->m_val == v)
				{
					auto p = m_left;
					this->m_left = p->m_right;
					delete p;
					return;
				}
				else if (m_left != nullptr) m_left->remove(v);
			}
			else if(v > m_val)
			{
				if (m_right != nullptr && m_right->m_val == v)
				{
					auto p = m_right;
					this->m_right = p->m_right;
					delete p;
					return;
				}
				else if(m_right != nullptr) m_right->remove(v);
			}
		}

		//function to search for specific value
		bool struct_contains(T v)
		{
			if (v == m_val)return true;//if there return found
			else if (v < m_val)//is key lower than current node value
			{
				if (m_left == nullptr) return false;//is next node null then key is not in tree
				else return m_left->struct_contains(v);//go further into tree and continue with search
			}
			else
			{
				if (m_right == nullptr) return false;//is next node null then key is not in tree
				return m_right->struct_contains(v);//go further into tree and continue with search
			}

		}
		//node constructor
		node(T val, node* left = nullptr, node* right = nullptr)
			: m_val(val), m_left(left), m_right(right) {}

		~node()
		{
		//	delete m_left;
		//	delete m_right;
                        //Create another Function to take the place of this destructor
			std::cout << "deleting " << this->m_val << std::endl;
		}

	};
private:
	node* root{ nullptr };
public:
	//node* root{nullptr};

	~tree()
	{
		std::cout << "tree destructor" << std::endl;
		delete root;
	}

	void insert(T v)
	{
		if (!root)
		{
			root = new node(v);
		}
		else
		{
			root->struct_insert(v);
		}
	}

	void r(T v)
	{
		if (root->m_val == v)
		{
                       // If the value is in the root
		}
		else root->remove(v);
	}

	bool contains(T v)
	{
		return root->struct_contains(v);
	}
};

int main() 
{
	tree<int> apple;
	std::random_device rd;
	std::mt19937 mersenne(rd());
	std::uniform_int_distribution<> q(1, 100);
	for (int i = 0; i < 100; i++)
	{
		int a = q(mersenne);
		apple.insert(a);
		if (a == 10)
			std::cout << "WE GOT IT\n";
	}
	apple.r(10);
}



You'll need a few implementations to get it working properly, but shouldn't be too difficult.
jamesfarrow (211)
Thanks! I will have a go at it. C++ is challenging to say the least, it certainly gets you thinking...
Just about of paper to scribble ideas on!!
Last edited on
dhayden (5798)
Removing from a binary tree is tricky. While it's necessary for a generic tree library, consider this: most of the time, you never remove items from the tree. You insert them, they stay there, and when you're done, you delete the entire tree. So remove() is a good learning exercise, but in practice, I rarely need it.
jamesfarrow (211)
Thanks everyone! I decided to look on YouTube for binary search tree and it became obvious that my approach, albeit not wrong per se, was harder to implement than the way it had been in the videos.
So I removed my struct form the class and put it in its own file, and re-wrote the tree class that it worked - in the way before re-write.
I then started to implement remove. I have to admit that it is a combination of my own work and 'plagiarism' in parts. The main thing is my previous remove function was along the right lines just harder to do the way I had set out. To be fair it makes more sense this way.

Thanks to everyone for taking time to post and help me!

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 

#ifndef node_hpp
#define node_hpp

#include <iostream>

template<typename T>
struct node
{
    node* m_left;
    node* m_right;
    T m_val;
    
    //node constructor
    node(T val, node* left=nullptr, node* right=nullptr)
    : m_val(val), m_left(left), m_right(right) {}
    
    //node destructor
    ~node()
     {
     delete m_left;
     delete m_right;
     std::cout << "deleting " << this->m_val << std::endl;
     }
    
    
};
//end of struct


#endif /* node_hpp */

//
//  main.cpp
//  binary tree
//


#include <iostream>
#include <random>
#include "tree.hpp"

int main(int argc, const char * argv[]) {
   
    tree<int> test;
    int node_to_remove{};
    for(int i{};i < 40; i++)
    {
        std::random_device dev;
        std::mt19937 mersenne(dev());
        std::uniform_int_distribution<int> dist(1, 100);
        test.insert(dist(dev));
    }
    
    
    //lower than root
    test.insert(25);
    test.insert(22);
    test.insert(13);
    test.insert(25);
    test.insert(11);
    test.insert(7);
    test.insert(23);
    test.insert(22);
    test.insert(42);
    test.insert(41);
    test.insert(31);
    test.insert(29);
    //higher than root
    test.insert(73);
    test.insert(58);
    test.insert(56);
    test.insert(57);
    test.insert(71);
    test.insert(91);
    test.insert(85);
    test.insert(78);
    test.insert(95);
    test.insert(94);
    test.insert(96);
    
    
    test.print();
    
    std::cout << "\n\ninput node to remove:- ";
    std::cin >> node_to_remove;
    
    test.setNodeKey(node_to_remove);
    
    if(test.contains(node_to_remove))
    {
        std::cout << "\n" << node_to_remove << " in tree" << std::endl;
    }
    else
    {
        std::cout << "\n" << node_to_remove << " not in tree" << std::endl;
    }
    
    
    test.remove(node_to_remove);
    
    test.print();
    
    if(test.contains(node_to_remove))
    {
       std::cout << "\n" << node_to_remove << " in tree" << std::endl;
    }
    else
    {
        std::cout << "\n" << node_to_remove << " not in tree" << std::endl;
    }
    
    return 0;
}
jamesfarrow (211)
My tree class is too long to post :(
jamesfarrow (211)
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 

#ifndef tree_hpp
#define tree_hpp
#include "node.hpp"

#include <iostream>
//left is less than
//right is greater than

template<typename T>
class tree
{
private:
    node<T>* root{nullptr};
    T nodeToRemoveKey;
    
    //function to remove the root of the tree and replace it
    void RemoveRootMatch()
    {
        if(root != nullptr)
        {
            node<T>* delPtr = root;
            int rootvalue = root->m_val;
            int smallestInRightSubtree;
            
            //case 0 - 0 children
            if(root->m_left == nullptr && root->m_right == nullptr)
            {
                root = nullptr;
                delete delPtr;
            }
            
            //case 1 - 1 child
            else if(root->m_left == nullptr && root->m_right != nullptr)
            {
                root = root->m_right;
                delPtr->m_right = nullptr;
                delete delPtr;
                std::cout << "root with value " << rootvalue << " was deleted" << std::endl;
                std::cout << "the new root contains " << root->m_val << std::endl;
            }
            else if(root->m_left != nullptr && root->m_right == nullptr)
            {
                root = root->m_left;
                delPtr->m_left = nullptr;
                delete delPtr;
                std::cout << "root with value " << rootvalue << " was deleted" << std::endl;
                std::cout << "the new root contains " << root->m_val << std::endl;
            }
            //case 2 - 2 children
            else
            {
                smallestInRightSubtree = FindSmallestPrivate(root->m_right);
                RemoveNodePrivate(smallestInRightSubtree, root);
                root->m_val = smallestInRightSubtree;
                std::cout << "the root key conating " << rootvalue <<
                " was overwritten with " << root->m_val << std::endl;
            }
        }
        else
        {
            std::cout << "can not remove root - tree empty" << std::endl;
        }
    }//end RmoveRootMatch function
    
    void RemoveMatch(node<T>* parent, node<T>* match, bool left)
    {
        if(root != nullptr)
        {
            node<T>* delPtr;
            int match_value = match->m_val;
            int smallestInRightSubtree;
            
            //case 0 - 0 children
            if(match->m_left == nullptr && match->m_right == nullptr)
            {
                delPtr = match;
                //is node to delete on the left or right of parent
                //then set that pointer to nullptr
                if(left == true)
                {
                    parent->m_left = nullptr;
                }
                else
                {
                    parent->m_right = nullptr;
                }
                //left == true ? parent->m_left = nullptr : parent->m_right = nullptr;
                delete delPtr;
                if(match_value == getNodeKey())
                {
                    std::cout << "node containing " << match_value<< " was removed" << std::endl;
                }
                else
                {
                    std::cout << "node containing " << getNodeKey() << " was overwritten";
                    std::cout << " with " << match_value  << ", and " << match_value <<
                    " was removed" << std::endl;
                }
            }
            //case 1 - 1 child
            else if(match->m_left == nullptr && match->m_right != nullptr)
            {
                //case for right child bit not a left child
                left == true ? parent->m_left = match->m_right : parent->m_right = match->m_right;
                match->m_right = nullptr;
                delPtr = match;
                delete delPtr;
                std::cout << "node containing " << match_value << " was removed" << std::endl;
            }
            else if(match->m_left != nullptr && match->m_right == nullptr)
            {
                //case for left child but not a right child
                left == true ? parent->m_left = match->m_left : parent->m_right = match->m_left;
                match->m_left = nullptr;
                delPtr = match;
                delete delPtr;
                std::cout << "node containing " << match_value << " was removed" << std::endl;
            }
            
            //case 2 - 2 children
            else
            {
                //std::cout << "here 2 children" << std::endl;
                smallestInRightSubtree = FindSmallestPrivate(match->m_right);
                RemoveNodePrivate(smallestInRightSubtree, match);
                match->m_val = smallestInRightSubtree;
            }
        }
        else
        {
            std::cout << "empty tree" << std::endl;
        }
    }
    
    void RemoveNodePrivate(T v, node<T>* parent)
    {
        if(root)//tree not empty
        {
            if(root->m_val == v)
            {
                RemoveRootMatch();
            }
            else
            {
                if(v < parent->m_val && parent->m_left != nullptr)
                {

                    if(parent->m_left->m_val == v)
                    {
                        RemoveMatch(parent, parent->m_left, true);
                    }
                    else
                    {
                        RemoveNodePrivate(v, parent->m_left);
                    }
                    
                }
                else if(v > parent->m_val && parent->m_right != nullptr)
                {
                    if(parent->m_right->m_val == v)
                    {
                        RemoveMatch(parent, parent->m_right, false);
                    }
                    else
                    {
                        RemoveNodePrivate(v, parent->m_right);
                    }
                }
                else
                {
                    std::cout << v << " was not found in tree" << std::endl;
                }
            }
            
        }
        else
        {
            std::cout << "tree is empty" << std::endl;
        }
    }//end RemoveNOdePrivate function
    
    
    
    int FindSmallestPrivate(node<T>* Ptr)
    {
        if(root == nullptr)
        {
            std::cout << "empty tree" << std::endl;
            return -1000;
        }
        else
        {
            if(Ptr->m_left != nullptr)
            {
                return FindSmallestPrivate(Ptr->m_left);
            }
            else
            {
                return Ptr->m_val;
            }
        }
    }
    
    //function to search for specific value
    bool PrivateContains(T v, node<T>* match)
    {
        if(v == match->m_val)return true;//if there return found
        else if(v < match->m_val)//is key lower than current node value
        {
            if(match->m_left == nullptr) return false;//is next node null then key is not in tree
            else return PrivateContains(v, match->m_left);//go further into tree and continue with search
        }
        else
        {
            if(match->m_right == nullptr) return false;//is next node null then key is not in tree
            return PrivateContains(v, match->m_right);//go further into tree and continue with search
        }
        
    }
    
    void PrivateInsert(T v, node<T>* insert)
    {
        if(v == insert->m_val) return;//case for item already in tree
        else if (v < insert->m_val)//is val less than current node
        {
            if (insert->m_left == nullptr)//is next node null then insert here
            {
                insert->m_left = new node(v);//insert
            }
            else PrivateInsert(v, insert->m_left);//continue further into tree
        }
        else
        {
            if(insert->m_right == nullptr)//is next node null then insert here
            {
                insert->m_right = new node(v);//insert
            }
            else PrivateInsert(v, insert->m_right);//continue further into tree
        }
        
    }
Pages: 12