Trees - Access Violation reading location 0xFEEEFEF2 for different set of numbers

[JekasG]

I have written up code for Tree with the implementation of adding and removing nodes from the tree. When I first tested the tree with a set of numbers then trying to remove numbers that are and aren't on that tree it worked perfectly fine. These were the number i used. 9, 5, 3, 6, 1, 8, 3, 1, 9, 3. I tried to remove 3 and it worked perfectly fine.

However when i used a different set of numbers 18, 82, 97, 16, 11, 9, 44, 86, 38, 74. Trying to remove 82 it throws the access violation error. But if i try to removed a number which isn't on the tree it works fine stating the predefined result that, that number doesn't exist in the tree.

Why is this so ?
Here is my code.

Main.cpp

#include <iostream>
#include "Tree.h"
using namespace std;

int main() {

	Tree<int> tree;

	int int_array[10] = { 18, 82, 97, 16, 11, 9, 44, 86, 38, 74 };
	int size = sizeof(int_array) / sizeof(int_array[0]);


	cout << "Elements that need to be added into a tree" << endl;
	for (int i = 0; i < size; i++) {
		cout << int_array[i] << " ";
	}

	cout << endl << endl;
	for (int i = 0; i < size; i++) {
		tree.Add(int_array[i]);
	}
	cout << endl;
	tree.Remove(82);

	int i_temp = 0;
	cin >> i_temp;

	return (0);
}

Node.h

#ifndef __NODE_H__
#define __NODE_H__

#include <iostream>

template <typename T>
class Node {
public:
	Node() {}
	Node(T data) {
		next_right_ = NULL;
		next_left_ = NULL;

		data_ = data;
	}
	~Node() {}

	void SetNextRight(Node<T>* next_right) {
		next_right_ = next_right;
	}
	Node* NextRight() {
		return next_right_;
	}
	void SetNextLeft(Node<T>* next_left) {
		next_left_ = next_left;
	}
	Node* NextLeft() {
		return next_left_;
	}

	void SetData(T data) {
		data_ = data;
	}
	T Data() const {
		return data_;
	}

private:
	Node<T>* next_right_;
	Node<T>* next_left_;

	T data_;
};
#endif // !__NODE_H__

Tree.h
#ifndef __TREE_H__
#define __TREE_H__

#include <iostream>
#include <algorithm>
#include "Node.h"

using namespace std;

template <typename T>
class Tree {
public:
	Tree() {}
	~Tree() {
		PostOrderDeletion(root_);
	}

	void Add(T data) {
		Add(root_, data);
	}

	void Remove(T data) {
		Remove(root_, data);
	}



private:
	void Add(Node<T>* current, T data) {

		if (root_ == NULL) {
			root_ = new Node<T>(data);
			cout << "Added " << data << " as the root" << endl;
			return;
		}
		else if (data <= current->Data()) {
			if (current->NextLeft() != NULL) {
				Add(current->NextLeft(), data);
			}
			else {
				current->SetNextLeft(new Node<T>(data));
				cout << "Added " << data << " as a child of " << current->Data() << endl;
			}
		}
		else if (data > current->Data()){
			if (current->NextRight() != NULL) {
				Add(current->NextRight(), data);
			}
			else {
				current->SetNextRight(new Node<T>(data));
				cout << "Added " << data << " as a child of " << current->Data() << endl;
			}
		}
	}

	void RemoveRoot() {
		if (root_ != NULL) {
			Node<T>* temp_root = root_;
			T temp_root_data = root_->Data();
			T temp_lowest_data;

			// Case of no children
			if (root_->NextLeft() == NULL && root_->NextRight() == NULL) {
				root_ = NULL;
				delete temp_root;
			}

			// Case of one child
			else if (root_->NextLeft() == NULL && root_->NextRight() != NULL) {
				root_ = root_->NextRight();
				delete temp_root;
				temp_root->SetNextRight(NULL);
				cout << "The root node with data " << temp_root_data <<
					" was deleted. The new root contains the data " << root_->Data() << endl;

			}
			else if (root_->NextLeft() != NULL && root_->NextRight() == NULL) {
				root_ = root_->NextLeft();
				delete temp_root;
				temp_root->SetNextLeft(NULL);
				cout << "The root node with data " << temp_root_data <<
					" was deleted. The new root contains the data " << root_->Data() << endl;
			}

			// Case of two children
			else {
				temp_lowest_data = FindLowest(root_->NextRight());
				Remove(root_, temp_lowest_data);
				root_->SetData(temp_lowest_data);
				cout << "The root node containing the data value " << temp_root_data <<
					" was overwritten with the data " << root_->Data() << endl;
			}

		}
		else {
			cout << "[Root Remove] - The tree is empty." << endl;
		}
	}

	void Remove(Node<T>* current, T data) {
		if (root_ != NULL) {
			if (data == root_->Data()) {
				RemoveRoot();
			}
			else {
				if (data <= current->Data() && current->NextLeft() != NULL) {
					(current->NextLeft())->Data() == data ?
						Remove(current, current->NextLeft(), true) :
						Remove(current->NextLeft(), data);
				}
				else if (data > current->Data() && current->NextRight() != NULL) {
					(current->NextRight())->Data() == data ?
						Remove(current, current->NextRight(), false) :
						Remove(current->NextRight(), data);
				}
				else {
					cout << "The data value " << data << " was not found" << endl;
				}
			}
		}
		else {
			cout << "[Remove Recursive] - The tree is empty." << endl;
		}
	}

	void Remove(Node<T>* current, Node<T>* match_test, bool is_left) {
		if (root_ != NULL) {
			Node<T>* delete_node;
			T match_data = match_test->Data();
			T lowest_data;

			// Case of no children
			if (match_test->NextLeft() == NULL && match_test->NextRight() == NULL) {
				delete_node = match_test;
				is_left == true ? current->SetNextLeft(NULL) : current->SetNextRight(NULL);
				delete delete_node;
				cout << "The node containing the data value " << match_data << " was removed" << endl;
			}

			// Case of one child
			if (match_test->NextLeft() == NULL && match_test->NextRight() != NULL) {
				is_left == true ? current->SetNextLeft(match_test->NextRight()) : current->SetNextRight(match_test->NextRight());
				match_test->SetNextRight(NULL);
				delete_node = match_test;
				delete delete_node;
				cout << "The node containing key " << match_data << " was removed" << endl;
			}
			else if (match_test->NextLeft() != NULL && match_test->NextRight() == NULL) {
				is_left == true ? current->SetNextLeft(match_test->NextLeft()) : current->SetNextRight(match_test->NextLeft());
				match_test->SetNextLeft(NULL);
				delete_node = match_test;
				delete delete_node;
				cout << "The node containing the data value " << match_data << " was removed" << endl;
			}
			else {
				lowest_data = FindLowest(match_test->NextRight());
				Remove(match_test, lowest_data);
				match_test->SetData(lowest_data);
			}
		}
		else {
			cout << "[Remove Match-Test] - The tree is empty." << endl;
		}
	}

	T FindLowest(Node<T>* current) {
		if (root_ != NULL) {
			if (current->NextLeft() != NULL) {
				return FindLowest(current->NextLeft());
			}
			else {
				cout << "The lowest value is " << current->Data() << endl;
				return current->Data();
			}
		}
		else {
			cout << "[Find Lowest] - The tree is empty" << endl;
			return NULL;
		}
	}

	void PostOrderDeletion(Node<T>* current) {
		if (current != NULL) {
			if (current->NextLeft() != NULL) {
				PostOrderDeletion(current->NextLeft());
			}
			if (current->NextRight() != NULL) {
				PostOrderDeletion(current->NextRight());
			}
			cout << "Deleting the node containing the data value " << current->Data() << endl;
			delete current;
		}
	}

	Node<T>* root_;

};
#endif // !__TREE_H__ 

[coder777]

Please use code tags: [code]Your code[/code]
Read this: http://www.cplusplus.com/articles/z13hAqkS/

This is definitely a problem:

delete temp_root;
temp_root->SetNextLeft(NULL);

You cannot do annything with temp_root after it is deleted. That causes undefined behavior.

[JekasG]

I've already tried commenting out all the delete temp_root
And the problem is still there

[MikeyBoy]

As coder777 said, please could you edit your original post to use code tags, to make your code easier to read. People are more likely to read it and help you, if you put in the effort to make your code readable.

[JekasG]

Hope that helps ~

[coder777]

The next problem is that root_ remains uninitialized. Set root_ to nullptr either on line 241 or 59.

Since you do not initialze next_right_ / next_left_ in your default constructor it is very likely that they remain uninitialized too.

Another problem is on line 182: You delete match_test (indirectly, why?) but you continue using it from line 187 on. Try return; after line 183.

[Ericool]

this is not smart ...

int int_array[10] = { 18, 82, 97, 16, 11, 9, 44, 86, 38, 74 };
int size = sizeof(int_array) / sizeof(int_array[0]);

before doing any deletion can you show us an initial array and then the output of this array when it's stored in the tree ? There is basicaly three recursive method to implement for that.

If the tree is not correctly set , then I dont see how you could do deletion well..

Thanks