#include using namespace std; template class bst { private: struct node { t data; node *left, *right; }; node *root = NULL; void pre(node *tmp) { if(tmp != NULL) { cout<< tmp->data<< " "; pre(tmp->left); pre(tmp->right); } } void in(node *tmp) { if(tmp != NULL) { in(tmp->left); cout<< tmp->data<< " "; in(tmp->right); } } void post(node *tmp) { if(tmp != nullptr) { post(tmp->left); post(tmp->right); cout<< tmp->data<< " "; } } int HeightHelp(node *tmp) { if(tmp == nullptr) return -1; int left = HeightHelp(tmp->left), right = HeightHelp(tmp->right); return (1 + max(left, right)); } int LevelsHelp(node *tmp) { if(tmp == nullptr) return 0; int left = LevelsHelp(tmp->left), right = LevelsHelp(tmp->right); return (1 + max(left, right)); } node* MaxHelp(node *tmp) { if(tmp == nullptr) return nullptr; else { while(tmp->right != nullptr) tmp = tmp->right; return tmp; } } node* MinHelp(node *tmp) { if(tmp == nullptr) return nullptr; else { while(tmp->left != nullptr) tmp = tmp->left; return tmp; } } public: void Display_pre() { cout<< "PreOrder : "; if(root == NULL) cout<< "tree is void"; else pre(root); cout<data = n; ptr->left = ptr->right = NULL; if(root == NULL) root = ptr; else { node *tmp = root, *prc; while(tmp != NULL) { prc = tmp; if(tmp->data > n) tmp = tmp->left; else tmp = tmp->right; } if(prc->data > n) prc->left = ptr; else prc->right = ptr; } } } void Delete(int n) { node *s = Searcha(n); if(!s) cout<< "this node is not Found"<data); if(root->left == prd) prd->right = root->right; else { prnt->right = prd->left; prd->left = root->left; prd->right = root->right; } root = prd; } else { if(s->left == nullptr && s->right == nullptr) { node *prnt = Parent(n); if(prnt->left == s) prnt->left = nullptr; else prnt->right = nullptr; delete s; } else if(s->left != nullptr && s->right != nullptr) { if(s->left == prd) { node *p = Parent(n); if(p->left == s) p->left = prd; else p->right = prd; prd->right = s->right; delete s; } else { node *pp = Parent(prd->data), *ps = Parent(n); pp->right = prd->left; prd->left = s->left; prd->right = s->right; if(ps->left == s) ps->left = prd; else ps->right = prd; delete s; } } else { node *p = Parent(n); if(s->left == NULL) { if(p->left == s) p->left = s->right; else p->right = s->right; delete s; } else { if(p->left == s) p->left = s->left; else p->right = s->left; delete s; } } } } } bool Searchb(int n) { node *tmp = root; while(tmp != nullptr) if(tmp->data == n) return true; else if(tmp->data > n) tmp = tmp->left; else tmp = tmp->right; return (tmp != NULL); } int Height() { if(root == NULL){ cout<< "tree is void"; return 0; } else return HeightHelp(root); } int Levels() { if(root == NULL){ cout<< "tree is void"; return 0; } else return LevelsHelp(root); } node* Searcha(int n) { node *tmp = root; while(tmp != NULL) if(tmp->data == n) return tmp; else if(tmp->data > n) tmp = tmp->left; else tmp = tmp->right; return NULL; } node* Max() { if(root == nullptr) return nullptr; else { node *tmp = root; while(tmp->right != nullptr) tmp = tmp->right; return tmp; } } node* Min() { if(root == nullptr) return nullptr; else { node *tmp = root; while(tmp->left != nullptr) tmp = tmp->left; return tmp; } } node* Parent(int n) { bool s = Searchb(n); if(!s) return nullptr; else { if(root->data == n) return nullptr; else { node *tmp = root, *prc = nullptr; while(tmp != nullptr) { prc = tmp; if(tmp->data > n) { tmp = tmp->left; if(tmp->data == n) return prc; } else { tmp = tmp->right; if(tmp->data == n) return prc; } } } } return nullptr; } node* Pred(int n) { node *s = Searcha(n); if(s == nullptr) return nullptr; else { if(s->left != nullptr) { node *m = MaxHelp(s->left); return m; } else { node *p = Parent(n); while(p->data > s->data) if(p == root) return nullptr; else p = Parent(p->data); return p; } } } node* Sec(int n) { node *s = Searcha(n); if(s == nullptr) return nullptr; else { if(s->right != nullptr) { node *m = MinHelp(s->right); return m; } else { node *p = Parent(n); while(p->data < s->data) if(p == root) return nullptr; else p = Parent(p->data); return p; } } } }; int main() { bst t; t.Display_pre(); t.Display_in(); t.Display_post(); t.Add(5); t.Add(4); t.Add(6); t.Display_pre(); t.Display_in(); t.Display_post(); cout<< "Height of this tree is : "<< t.Height()<data<data<data<data<data<data<data<

Binary Search Tree on c++