Hamed Kiani (Ph.D.)
  • Home
  • Publications
  • Contact

A class implementation of Binary Search Tree in C++

9/18/2015

10 Comments

 
  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
/******************************************************************************************
*******************************************************************************************
Chapter 4 Trees and Graphs

This is a class implementation of Binary Search Tree (BST), containing:

   inser(): insert a value in a BST
   isBalanced(): check if a BST is balanced, a BST is balanced if the difference of left and right subtrees height is atmost one!
   getHeight(): returns the height of a BST
   deleteBST(): deletes a BST      
   inOrder():      prints a BST i in-order fashion
   preOrder(): prints a BST i pre-order fashion
   postOrder(): prints a BST i post-order fashion

By: Hamed Kiani (Sep. 18, 2015)
******************************************************************************************
******************************************************************************************/

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

// tree node, including left and right pointers, data 
struct Node{
        Node(int value): data(value), left(NULL), right(NULL) {}
        int data;
        Node *left;
        Node *right;
};

/////////////////////////////////////////////////////////////////////////////////////////
// BST class
class BST{
private:
        Node *_root;
        void insert(Node *treeNode, int data);
        bool isBalanced(Node *treeNode);
        int  getHeight(Node *treeNode);
        void deleteBST(Node *treeNode);
        void inOrder(Node * treeNode);
        void preOrder(Node * treeNode);
        void postOrder(Node * treeNode);
public:

        BST();  // constructor     
        ~BST();     // destractor

        void insert(int data){ insert(_root, data);}       

        int getHeight(){return getHeight(_root);}
        Node * getMaxNode();
        Node * getMinNode();

        void deleteBST() {deleteBST(_root);}

        bool isBalanced(){return isBalanced(_root);        }

        void inOrder() {inOrder(_root);}
        void preOrder(){preOrder(_root);}
        void postOrder(){postOrder(_root);}
};

/////////////////////////////////////////////////////////////////////////////////////////
BST::BST()
{
        _root = NULL;
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::insert(Node *treeNode, int data)
{
        if (!treeNode)
        {
                treeNode = new Node(data);           
                _root = treeNode;           
        }
        else
        {
                if (data < treeNode->data)
                {
                        if (!treeNode->left)
                        {
                                Node *treeTemp = new Node(data);
                                treeNode->left = treeTemp;
                        }
                        else
                                insert(treeNode->left, data);
                }
                else
                {
                        if (!treeNode->right)
                        {
                                Node *treeTemp = new Node(data);                         
                                treeNode->right = treeTemp;
                        }
                        else
                                insert(treeNode->right, data);
                }
        }
}

/////////////////////////////////////////////////////////////////////////////////////////
int BST::getHeight(Node *treeNode)
{
        if (!treeNode)
                return 0;
        return 1 + max(getHeight(treeNode->left) , getHeight(treeNode->right));
}

/////////////////////////////////////////////////////////////////////////////////////////
bool BST::isBalanced(Node *treeNode)
{
        if (!treeNode)
                return false;
        int leftHeight = getHeight(treeNode->left);
        int rightHeight = getHeight(treeNode->right);

        if (abs(leftHeight - rightHeight) > 1)
                return false;
        return true;
}

/////////////////////////////////////////////////////////////////////////////////////////
Node * BST::getMaxNode()
{
        if (!_root)
        {
                cout <<  " the BST is empty!" << endl;
                return NULL;
        }
        Node * treeNode = _root;
        while(treeNode->right)
                treeNode = treeNode ->right;
        return treeNode;
}

/////////////////////////////////////////////////////////////////////////////////////////
Node * BST::getMinNode()
{
        if (!_root)
        {
                cout <<  " the BST is empty!" << endl;
                return NULL;
        }
        Node * treeNode = _root;
        while(treeNode->left)
                treeNode = treeNode ->left;
        return treeNode;
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::deleteBST(Node *treeNode) 
{
        if (!treeNode)
                return;

        Node * curTreeNode = treeNode;
        Node * leftTreeNode = treeNode->left;
        Node * rightTreeNode = treeNode->right;
        delete(curTreeNode);
        deleteBST(leftTreeNode);
        deleteBST(rightTreeNode);
}

/////////////////////////////////////////////////////////////////////////////////////////
BST::~BST()
{
        deleteBST();
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::inOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        inOrder(treeNode->left);
        cout << treeNode->data << " " ;
        inOrder(treeNode->right);
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::preOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        cout << treeNode->data << " ";
        preOrder(treeNode->left);
        preOrder(treeNode->right);
}

/////////////////////////////////////////////////////////////////////////////////////////
void BST::postOrder(Node * treeNode)
{
        if (!treeNode)
                return;
        postOrder(treeNode->left);
        postOrder(treeNode->right);
        cout << treeNode->data << " ";
}

/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
        BST myBST;
        myBST.insert(5);
        myBST.insert(10);
        myBST.insert(3);

        myBST.insert(51);
        myBST.insert(110);
        myBST.insert(13);
        
        int h = myBST.getHeight();
        cout << "the height of this BSt is : " << h << endl;

        Node * mx = myBST.getMaxNode();
        cout << "max value: " << mx->data << endl;

        Node * mi = myBST.getMinNode();
        cout << "min value: " << mi->data << endl;

        bool isbal = myBST.isBalanced();
        if (isbal)
                cout << "BST is balanced! " << endl;
        else
                cout << "BST is not balanced! " << endl;

        cout << " in-order traverse is : " << endl;
        myBST.inOrder();cout << endl;
        cout << " pre-order traverse is : " << endl;
        myBST.preOrder();cout << endl;
        cout << " post-order traverse is : " << endl;
        myBST.postOrder();cout << endl;
}
10 Comments
Muhammad Umer Farooq link
11/12/2018 12:47:53 am

What happen if insert number is equal to previous number enter in tree??

Reply
Bhavesh Pawar
1/7/2020 12:40:41 am

then code becomes more complicated so right now we need to consider that user gives us unique data

Reply
Anand Mishra
1/7/2020 12:47:33 am

keep your fucking mouth off dont interfair in anothers fucking life you bc

Bhavesh Pawar
1/7/2020 12:39:10 am

please give codes which are understandable to the user

Reply
Soham Kamthe
1/7/2020 12:42:35 am

if you are getting then get us some easy codes in yopur own laguage

Reply
Maria Chase link
12/23/2020 09:06:27 pm

I enjoyeed reading your post

Reply
Brij Bhushan link
4/7/2021 12:14:42 am

Indeed I found this article more informative, thanks for sharing this article.

Reply
John Cole
8/28/2023 11:38:24 am

Thanks for sharing !!

Reply
grainme
6/23/2024 12:59:05 pm

isBalanced is wrong.

Base case should be True - an empty tree is considered balanced!
and last return should be isBalanced(left side) && isBalanced(right side) as every other subtree should be balanced!

Reply
Karas Kitchen link
10/3/2024 10:56:59 am

First time reading this blog thanks for sharing.

Reply



Leave a Reply.

    A place to practice the coding interview.

    Author

    Hamed Kiani

    Categories

    All
    Arrays And Strings
    Linked List
    Stack And Queue
    Trees And Graphs

    Archives

    September 2015
    July 2015

    RSS Feed

Copyright © 2020, Hamed Kiani