C++

Forum

 
Binary Search Tree Assistance

fi50 (23)
Okay, I've spent about an hour looking at this and I have no idea why it won't work. The findElement function is buggy, sometimes it finds the value sometimes it doesn't. I'm assuming it's something blindingly obvious so if anyone could point out where I've cocked up you have bragging rights.

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
 
 struct node
{
	int value;

	node* p_left;
	node* p_right;
};

node* addElement(node* tree, int userValue);
node* findElement(node* tree, int valuetoFind);

node* head = NULL;

int main()
{
	cout << "Enter a number to add to the tree. Press 0 to skip." << endl;
	int inputValue;
	cin >> inputValue;

	head = addElement(head, inputValue);

	cin >> inputValue;

	while (inputValue != 0)
	{
		addElement(head, inputValue);
		cin >> inputValue;
	}

	cout << "Enter a number to find. Press 0 to skip." << endl;

	int toFind;
	cin >> toFind;
	if (toFind != 0)
	{
		findElement(head, toFind);
	}

	system("PAUSE");

}

node* addElement(node* tree, int userValue)
{
	if (tree == NULL)
	{
		node* newNode = new node;
		newNode->value = userValue;
		newNode->p_left = NULL;
		newNode->p_right = NULL;
		return newNode;
	}
	
	if (userValue < tree->value)
	{
		tree->p_left = addElement(tree->p_left, userValue);
	}
	else if (userValue > tree->value)
	{
		tree->p_right = addElement(tree->p_right, userValue);
	}
}

node* findElement(node* tree, int valuetoFind)
{
	if (tree == NULL)
	{
		cout << "The value you entered could not be found." << endl;
		return NULL;
	}
	else if (valuetoFind == tree->value)
	{
		cout << "The value " << valuetoFind << " was found." << endl;
		return tree;
	}
	else if (valuetoFind < tree->value)
	{
		return findElement(tree->p_left, valuetoFind);
	}
	else
	{
		return findElement(tree->p_right, valuetoFind);
	}
	
}
Last edited on
AbstractionAnon (6954)
A couple of questions:

What value is returned for node * at line 61 if line 44 is false?

What value is returned for node * at line 83 if line 70 is true?


Last edited on
fi50 (23)
Hey, thanks for your reply. Well, at the moment, as you can see, nothing is returned at either line 44 or line 70. It's not exactly great programming but I think that all possible outcomes are covered by the else if and else statements.
ResidentBiscuit (4459)
In addElement, you're not covering all paths. What if userValue == tree->value ?

What value is returned for node * at line 83 if line 70 is true?

He's right, you're not returning anything from this method in this branch.

What input are you providing? I'm not able to recreate the issue.
Last edited on
fi50 (23)
Okay, I've changed it so that the tree is returned if 70 is true.
ResidentBiscuit (4459)
Edit your original post reflecting the change.
fi50 (23)
I'm not sure if I've made the problem clear. Here's an example, if I enter the numbers 3, 1, 2 in that order and then search for the number 1 it outputs: "The value you entered cannot be found."

Edit: I updated the original post.
Last edited on
ResidentBiscuit (4459)
That exact input worked for me.

residentbiscuit@work-debian:~$ ./test 
Enter a number to add to the tree. Press 0 to skip.
3
1
2
0
Enter a number to find. Press 0 to skip.
1
The value 1 was found.


What compiler and platform are you using? I'm not sure if using NULL for a null pointer is standard.
Last edited on
fi50 (23)
That's really odd. I just tried it again and got "The value you entered cannot be found."
ResidentBiscuit (4459)
Change those NULLs to either 0, or nullptr_t if you're on a c++11 compliant compiler.
fi50 (23)
I changed them all to 0 and got the same result. This is going to sound far fetched, but is it possible that it could be a hardware fault?
ResidentBiscuit (4459)
It is very highly unlikely. So much so that I would say no. What platform and compiler are you using?
fi50 (23)
Windows 7 and MS Visual Studio 2013 which I'm pretty sure just uses the Visual Studio compiler.
Last edited on
Topic archived. No new replies allowed.