### 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.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287`` ``````//Michaela Ervin - Tree ADT #ifndef H_TREE #define H_TREE #include #include "stack.h" template struct leaf { dType _id; leaf *_left, *_right; }; const int MAXSTACK = 15; template class tree { template friend std::ostream& operator<< (std::ostream& outs, const tree& tree); protected: leaf* _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* _p, leaf* _l); void delete_one(leaf* _p, leaf* _l); void delete_two(leaf* _l); void inorderR(leaf* _l, std::ostream& outs) const; void preorderR(leaf* _l, std::ostream& outs) const; void postorderR(leaf* _l, std::ostream& outs) const; void hexxus(leaf*& _l); }; template tree::tree():_root(NULL) {} template std::ostream& operator<< (std::ostream& outs, const tree& tree) { //Put stuff to do here! return outs; } template bool tree::isEmpty() const{return (_root == NULL);} template void tree::grow(dType _water) { leaf *_l, *_t, *_n; _n = new leaf; _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 void tree::prune(dType _todel) { leaf *_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 void tree::delete_zero(leaf* _p, leaf* _l) { if (_p->_left == _l) _p->_left = NULL; else _p->_right = NULL; delete _l; } template void tree::delete_one(leaf* _p, leaf* _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 void tree::delete_two(leaf* _l) { leaf *_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 void tree::inordertraversalR(std::ostream& outs) const{inorderR(_root, outs);} template void tree::inorderR(leaf* _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 void tree::preordertraversalR(std::ostream& outs) const{preorderR(_root, outs);} template void tree::preorderR(leaf* _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 void tree::postordertraversalR(std::ostream& outs) const{postorderR(_root, outs);} template void tree::postorderR(leaf* _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 void tree::inordertraversalI(std::ostream& outs) const { if (!isEmpty()) { stack*> _logs(MAXSTACK, NULL); leaf *_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 void tree::preordertraversalI(std::ostream& outs) const { if (!isEmpty()) { stack*> _logs(MAXSTACK, NULL); leaf *_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 int tree::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 tree::~tree(){hexxus(_root);} template void tree::killtree(){hexxus(_root);} template void tree::hexxus(leaf*& _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.

 ``123`` ``````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