Find the minimum data of binary tree

I want a recursive function that returns a pointer pointing to the node which has the minimum data in the binary tree.

That's what I wrote:

struct CP {
int data; // data of the node
CP * left; // pointer to the left subtree
CP * right; // pointer to the right subtree
};

typedef CP * CPPtr;

CPPtr MinValue(CPPtr SP){

if(SP->left!=NULL || SP->right!=NULL){
if(SP->data < SP->left->data && SP->data < SP->right->data){
return SP;
}
else if(SP->left->data < SP->data && SP->left->data < SP->right->data){
return SP->left;
}
else if(SP->right->data < SP->left->data && SP->right->data < SP->data){
return SP->right;
}
}
else return SP;
}

It can only find one side of the binary tree. Can someone help me how to do with the code? Thank you very much!
can someone help me?
Have a look at this excellent and easy to understand article by Alex Allain on binary trees. It should anwser your question I think.

http://www.cprogramming.com/tutorial/lesson18.html

Mike
Last edited on
since you asked, here is the code. It is your homework to find and edit the parts you need.

The function and var names are based on ferngully. Get it, tree, ferngully, ha ha.

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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
//Michaela Ervin - Tree ADT

#ifndef H_TREE
#define H_TREE

#include <iostream>
#include "stack.h"

template <class dType>
struct leaf
{
	dType _id;
	leaf<dType> *_left, *_right;
};

const int MAXSTACK = 15;

template <class dType>
class tree
{
	template <class dType> friend std::ostream& operator<< (std::ostream& outs, const tree<dType>& tree);
protected:
	leaf<dType>* _root;
public:
	tree();
	bool isEmpty() const;
	void grow(dType _water);
	void prune(dType _todel);
	void inordertraversalR(std::ostream& outs) const;
	void preordertraversalR(std::ostream& outs) const;
	void postordertraversalR(std::ostream& outs) const;
	void inordertraversalI(std::ostream& outs) const;
	void preordertraversalI(std::ostream& outs) const;
	int countR(node* _root);
	void killtree();
	~tree();
private:
	void delete_zero(leaf<dType>* _p, leaf<dType>* _l);
	void delete_one(leaf<dType>* _p, leaf<dType>* _l);
	void delete_two(leaf<dType>* _l);
	void inorderR(leaf<dType>* _l, std::ostream& outs) const;
	void preorderR(leaf<dType>* _l, std::ostream& outs) const;
	void postorderR(leaf<dType>* _l, std::ostream& outs) const;
	void hexxus(leaf<dType>*& _l);
};

template <class dType>
tree<dType>::tree():_root(NULL) {}

template <class dType>
std::ostream& operator<< (std::ostream& outs, const tree<dType>& tree)
{
	//Put stuff to do here!
	return outs;
}

template <class dType>
bool tree<dType>::isEmpty() const{return (_root == NULL);}

template <class dType>
void tree<dType>::grow(dType _water)
{
	leaf<dType> *_l, *_t, *_n;
	_n = new leaf<dType>;

	_n->_id = _water;
	_n->_left = NULL;
	_n->_right = NULL;

	if (!isEmpty())
	{
		_l = _root;
		while (_l != NULL)
		{
			_t = _l;
			if (_water < _l->_id)
				_l = _l->_left;
			else if (_water > _l->_id)
				_l = _l->_right;
		}
		if (_t->_id > _water)
			_t->_left = _n;
		else
			_t->_right = _n;
	}
	else
		_root = _n;
}

template <class dType>
void tree<dType>::prune(dType _todel)
{
	leaf<dType> *_l, *_p;
	_p = NULL;
	_l = _root;
	
	while (_l != NULL && _l->_id != _todel)
	{
		_p = _l;
		if (_todel < _l->_id)
			_l = _l->_left;
		else
			_l = _l->_right;
	}
	if (_l != NULL)
	{
		if (_l->_left == NULL && _l->_right == NULL)
			delete_zero(_p, _l);
		else if (_l->_left != NULL && _l->_right != NULL)
			delete_two(_l);
		else
			delete_one(_p, _l);
	}
	else
		std::cout << "Node w/ id: " << _todel << " is not in the tree...";
}

template <class dType>
void tree<dType>::delete_zero(leaf<dType>* _p, leaf<dType>* _l)
{
	if (_p->_left == _l)
		_p->_left = NULL;
	else
		_p->_right = NULL;
	delete _l;
}

template <class dType>
void tree<dType>::delete_one(leaf<dType>* _p, leaf<dType>* _l)
{
	if (_p->_left == _l)
		if (_l->_left != NULL)
			_p->_left = _l->_left;
		else
			_p->_left = _l->_right;
	else if (_p->_right == _l)
		if (_l->_left != NULL)
			_p->_right = _l->_left;
		else
			_p->_right = _l->_right;
}

template <class dType>
void tree<dType>::delete_two(leaf<dType>* _l)
{
	leaf<dType> *_s;
	dType _holder;

	_s = _l->_left;
	while (_s->_right != NULL)
	{
		if (_s->_right != NULL)	
			_s = _s->_right;
		else
			_s = _s->_left;
	}
	_holder = _s->_id;
	prune(_s->_id);
	_l->_id = _holder;
}

template <class dType>
void tree<dType>::inordertraversalR(std::ostream& outs) const{inorderR(_root, outs);}

template <class dType>
void tree<dType>::inorderR(leaf<dType>* _l, std::ostream& outs) const
{
	if (!isEmpty())
	{
		if (_l->_left != NULL) inorderR(_l->_left, outs);
		outs << _l->_id << " ";
		if (_l->_right != NULL) inorderR(_l->_right, outs);
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::preordertraversalR(std::ostream& outs) const{preorderR(_root, outs);}

template <class dType>
void tree<dType>::preorderR(leaf<dType>* _l, std::ostream& outs) const
{
	if (!isEmpty())
	{
		outs << _l->_id << " ";
		if (_l->_left != NULL) preorderR(_l->_left, outs);
		if (_l->_right != NULL) preorderR(_l->_right, outs);
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::postordertraversalR(std::ostream& outs) const{postorderR(_root, outs);}

template <class dType>
void tree<dType>::postorderR(leaf<dType>* _l, std::ostream& outs) const
{
	if (!isEmpty())
	{
		if (_l->_left != NULL) postorderR(_l->_left, outs);
		if (_l->_right != NULL) postorderR(_l->_right, outs);
		outs << _l->_id << " ";
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::inordertraversalI(std::ostream& outs) const
{
	if (!isEmpty())
	{
		stack<leaf<dType>*> _logs(MAXSTACK, NULL);
		leaf<dType> *_l = _root;

		while (!_logs.isEmpty() || _l != NULL)
			if ( _l != NULL)
			{
				_logs.push(_l);
				_l = _l->_left;
			}
			else
			{
				_l = _logs.pop();
				outs << _l->_id << " ";
				_l = _l->_right;
			}
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::preordertraversalI(std::ostream& outs) const
{
	if (!isEmpty())
		{
			stack<leaf<dType>*> _logs(MAXSTACK, NULL);
			leaf<dType> *_l = _root;

			while (!_logs.isEmpty() || _l != NULL)
				if ( _l != NULL)
				{
					outs << _l->_id << " ";
					_logs.push(_l);
					_l = _l->_left;
				}
				else
				{
					_l = _logs.pop();
					_l = _l->_right;
				}
		}
		else
			outs << "The tree has not grown yet...";	
}

template <class dType>
int tree<dType>::countR(node* _root)
{
	if (!isEmpty())
	{
		if (_l->_left != NULL) return 1 + countR(_l->_left, outs);
		if (_l->_right != NULL) return 1 + countR(_l->_right, outs);
	}
}

template <class dType>
tree<dType>::~tree(){hexxus(_root);}

template <class dType>
void tree<dType>::killtree(){hexxus(_root);}

template <class dType>
void tree<dType>::hexxus(leaf<dType>*& _l)
{
	if (_l != NULL)
	{
		hexxus(_l->_left);
		hexxus(_l->_right);
		delete _l;
		_l = NULL;
	}
}
#endif 

@Michaela Elise (21)



I think you are going to give ppendless (2) a heart attack
well indeed.....
lol, well, ppendless, you should be able to find the recursive traversals (Hint they either end with an R or I) bet you can guess which one is recursive. LOL. Just edit one of them to store the min value.

1
2
3
CP* min;
if(CP->value < current->value)
    CP = current;


you will need go initialize min, whatever the first node is, most likely root, is fine.
Last edited on
comments are for sissies :D
LOL @ Smac89

It is a basic bstree, other than my 'at-the-time' variable names.
Last edited on
Topic archived. No new replies allowed.