Web
Analytics Made Easy - StatCounter

Binary Search Trees (BST) with code in C++, Python, and Java

Introduction

The binary search tree is a binary tree with the following property.

Every node in the left subtree of a node x are less than or equal to x and every node in the right subtree are greater than or equal to x.

When I say node I mean the data (or key) of the node. This property is called a binary search property and the binary tree is, therefore, called a binary search tree. Figure 1 shows an example of a binary search tree.

Fig 1: An example of a binary search tree

If you look at any node in the figure, the nodes in the left subtree are less or equal to the node and the nodes in the right subtree are greater than or equal to the node. The height of a randomly generated binary search tree is O(log n). Due to this, on average, operations in binary search tree take only O(log n) time.

Some binary trees can have the height of one of the subtrees much larger than the other. In that case, the operations can take linear time. The examples of such binary trees are given in Figure 2.

Fig 2: The examples of unbalanced binary search tree

But, on average, the height of the BST is O(log n).

In the next section, I explain the operations on BST in detail.

Operations on BST

The summary of the operations I am going to discuss and their running times are outlined in the table below.

S. No.OperationAverage CaseWorst Case
1SearchO(log n)O(n)
2MinimumO(log n)O(n)
3MaximumO(log n)O(n)
4PredecessorO(log n)O(n)
5SuccessorO(log n)O(n)
6InsertO(log n)O(n)
7DeleteO(log n)O(n)

The working details of these operations are explained below.

Search Operation

We can search a node with a given key (data) on a binary search tree. We start the process from the root node and move downward until we find the key we are searching for. If we find the node, the process terminates otherwise we return NIL. For each node x we encounter, we compare the key k with x.key. If the two keys are equal, the search terminates. If k is smaller than x.key, the search continues in the left subtree of x. Similarly, if k is larger than x.key, the search continues in the right subtree. Figure 3 illustrates this process with an example where we are searching for a node with key 25.

Fig 3: Illustrating the search on BST

The recursive algorithm for the search operation is given below.

TREE-SEARCH(x, k)
     if x == NIL or k == x.key
         return x
     if k < x.key
         return TREE-SEARCH(x.left, k)
     else return TREE-SEARCH(x.right, k)

The running time of the search procedure is O(h) where h is the height of the tree.

Minimum and Maximum

Given a binary search tree, we can find a node whose key is minimum by following the left child pointers from the root all the way down to the leaf node. Similarly, we can find the key whose key is maximum by following the right child pointers. In other words, the left-most node of a left subtree as the minimum key and the right-most node of a right subtree has the maximum key. Figure 4 illustrates this with an example tree.

Fig 4: Illustrating the minimum and maximum operations

An algorithm to find the node with minimum key is presented below.

TREE-MINIMUM(x)
     while x.left != NIL
         x = x.left
     return x

The algorithm for the maximum is symmetric.

TREE-MAXIMUM(x)
     while x.right != NIL
         x = x.right
     return x

The running time of TREE-MINIMUM and TREE-MAXIMUM is O(h) where h is the height of the tree.

Successor and Predecessor

The successor of a node in a binary search tree is a node whose key is next key in the sorted order determined by an in-order walk. That means, if we sort the nodes based on the key in increasing order (in-order walk), each node is the successor of the preceding node. Similarly, each node is the predecessor of the following node. Due to the structure of the binary search tree, we can find the successor and predecessor of a node without comparing the keys.

To find the successor of a node x with key x.key, we do the following.

  1. If the right subtree of node x is non-empty, then the successor of x is just the leftmost node in x‘s right subtree.
  2. If the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x.

In a similar way, to find the predecessor of a node x with key x.key, we do the following.

  1. If the left subtree of node x is non-empty, then the successor of x is just the rightmost node in x‘s left subtree.
  2. If the left subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose right child is also an ancestor of x.

The algorithm to find the successor y of a node x is given below.

TREE-SUCCESSOR(x)
     if x.right != NIL
         return TREE-MINIMUM(x.right)
     y = x.parent
     while y != NIL and x == y.right
         x = y
         y = y.parent
return y

Similarly, the algorithm to find the predecessor y of the node x is

TREE-PREDECESSOR(x)
     if x.left != NIL
         return TREE-MAXIMUM(x.left)
     y = x.parent
     while y != NIL and x == y.left
         x = y
         y = y.parent
return y

Both TREE-SUCCESSOR and TREE-PREDECESSOR take O(h) time to run.

Insertion

The insertion operation inserts a node in the appropriate position so that the binary search tree property is not violated. To insert a node z in the tree, we compare z with node x starting from the root node. If z.key is smaller than x.key, we continue the process in the left subtree otherwise we move to the right subtree. We continue this process until the value of x is NIL. To make the process simple, we also need to keep track of the previous value y of x. When x is NIL, we compare key of y to the key of z and make z left or right child depending upon which one is larger. Figure 5 illustrates this process.

Fig 5: Illustrating the insertion operation

The algorithm for insertion operation is given below.

TREE-INSERT(z)
     y = NIL
     x = root
     while x != NIL
         y = x
         if z.key < x.key
             x = x.left
         else x = x.right
     z.parent = y
     if y == NIL
         root = z
     elseif z.key < y.key
         y.left = z
     else y.right = z

The running time of this operation is O(h) since we travel down the tree following a simple path.

Deletion

The deletion operation is a little bit tricky as we need to conserve the BST property after we delete the node. We may need to transform the tree in order to conserve the BST property. We need to handle three different cases in order to delete a node x. First two cases are simple and the last one is a little bit difficult.

  • Case 1: When x is a leaf node, we simply delete the node and change the x’s parent node’s left and right pointer accordingly.
  • Case 2: When x has only one child (either left or right), we delete the node x and set the parent node’s left or right pointer to the x’s child node. Similarly, we adjust the parent pointer of x’s child node.
  • Case 3: When x has both the children then we do the following.
    1. We copy the minimum node y of x’s right subtree and place it in the place of x.
    2. Delete y. In deleting y, we need to handle either case 1 or case 2 depending upon whether y has one child or doesn’t have any children.

Let me explain the case 3 with the help of an example.

Fig 6: Illustrating the case 3 of the deletion procedure.

The algorithm for the deletion is given below.

TREE-DELETE(node, key)
     if node == NIL
         return node
     elseif key < node.key
         node.left = TREE-DELETE(node.left, key)
     elseif key > node.key
         node.right = TREE-DELETE(node.right, key)
     else
         //case 1
         if node.left == NIL and node.right == NIL
             delete node
             node = NIL
         // case 2
         elseif node.left == NIL
             temp = node
             node = node.right
             delete temp
         elseif node.right == NIL
             temp = node
             node = node->left
             delete temp
         // case 3
         else
             temp = TREE-MINIMUM(node.right)
             node.key = temp.key
             node.right = TREE-DELETE(node.right, temp.key)
     return node

The complexity of the deletion procedure is O(h).

Tree Sort

One interesting application of binary search tree is in the tree sort. The in-order traversal of BST results into the sorted order of the keys. This is known as the tree sort and the complexity of this sort is O(nh).

Implementation

The C++, Java, and Python implementations of the binary search tree is presented below.

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
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
// Binary search tree implementation in C++
// Author: Algorithm Tutor

#include <iostream>

using namespace std;

// data structure that represents a node in the tree
struct Node {
int data; // holds the key
Node *parent; // pointer to the parent
Node *left; // pointer to left child
Node *right; // pointer to right child
};

typedef Node *NodePtr;

// class BST implements the operations in BST
class BST {
private:
NodePtr root;

// initializes the nodes with appropirate values
// all the pointers are set to point to the null pointer
void initializeNode(NodePtr node, int key) {
node->data = key;
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
}

void preOrderHelper(NodePtr node) {
if (node != nullptr) {
cout<<node->data<<" ";
preOrderHelper(node->left);
preOrderHelper(node->right);
}
}

void inOrderHelper(NodePtr node) {
if (node != nullptr) {
inOrderHelper(node->left);
cout<<node->data<<" ";
inOrderHelper(node->right);
}
}

void postOrderHelper(NodePtr node) {
if (node != nullptr) {
postOrderHelper(node->left);
postOrderHelper(node->right);
cout<<node->data<<" ";
}
}

NodePtr searchTreeHelper(NodePtr node, int key) {
if (node == nullptr || key == node->data) {
return node;
}

if (key < node->data) {
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}

NodePtr deleteNodeHelper(NodePtr node, int key) {
// search the key
if (node == nullptr) return node;
else if (key < node->data) node->left = deleteNodeHelper(node->left, key);
else if (key > node->data) node->right = deleteNodeHelper(node->right, key);
else {
// the key has been found, now delete it

// case 1: node is a leaf node
if (node->left == nullptr && node->right == nullptr) {
delete node;
node = nullptr;
}

// case 2: node has only one child
else if (node->left == nullptr) {
NodePtr temp = node;
node = node->right;
delete temp;
}

else if (node->right == nullptr) {
NodePtr temp = node;
node = node->left;
delete temp;
}

// case 3: has both children
else {
NodePtr temp = minimum(node->right);
node->data = temp->data;
node->right = deleteNodeHelper(node->right, temp->data);
}

}
return node;
}

void printHelper(NodePtr root, string indent, bool last) {
// print the tree structure on the screen
if (root != nullptr) {
cout<<indent;
if (last) {
cout<<"└────";
indent += " ";
} else {
cout<<"├────";
indent += "| ";
}

cout<<root->data<<endl;

printHelper(root->left, indent, false);
printHelper(root->right, indent, true);
}
}

public:
BST() {
root = nullptr;
}

void createSampleTree1() {
NodePtr node50 = new Node;
initializeNode(node50, 50);
NodePtr node30 = new Node;
initializeNode(node30, 30);
NodePtr node70 = new Node;
initializeNode(node70, 70);

node30->parent = node50;
node70->parent = node50;
node50->left = node30;
node50->right = node70;

NodePtr node23 = new Node;
initializeNode(node23, 23);
NodePtr node35 = new Node;
initializeNode(node35, 35);

node23->parent = node30;
node35->parent = node30;
node30->left = node23;
node30->right = node35;

NodePtr node11 = new Node;
initializeNode(node11, 11);
NodePtr node25 = new Node;
initializeNode(node25, 25);

node11->parent = node23;
node25->parent = node23;
node23->left = node11;
node23->right = node25;

NodePtr node31 = new Node;
initializeNode(node31, 31);
NodePtr node42 = new Node;
initializeNode(node42, 42);

node31->parent = node35;
node42->parent = node35;
node35->left = node31;
node35->right = node42;

NodePtr node80 = new Node;
initializeNode(node80, 80);

node80->parent = node70;
node70->right = node80;

NodePtr node73 = new Node;
initializeNode(node73, 73);
NodePtr node85 = new Node;
initializeNode(node85, 85);

node73->parent = node80;
node85->parent = node80;
node80->left = node73;
node80->right = node85;

this->root = node50;
}

// Pre-Order traversal
// Node->Left Subtree->Right Subtree
void preorder() {
preOrderHelper(this->root);
}

// In-Order traversal
// Left Subtree -> Node -> Right Subtree
void inorder() {
inOrderHelper(this->root);
}

// Post-Order traversal
// Left Subtree -> Right Subtree -> Node
void postorder() {
postOrderHelper(this->root);
}

// search the tree for the key k
// and return the corresponding node
NodePtr searchTree(int k) {
return searchTreeHelper(this->root, k);
}

// find the node with the minimum key
NodePtr minimum(NodePtr node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}

// find the node with the maximum key
NodePtr maximum(NodePtr node) {
while (node->right != nullptr) {
node = node->right;
}
return node;
}

// find the successor of a given node
NodePtr successor(NodePtr x) {
// if the right subtree is not null,
// the successor is the leftmost node in the
// right subtree
if (x->right != nullptr) {
return minimum(x->right);
}

// else it is the lowest ancestor of x whose
// left child is also an ancestor of x.
NodePtr y = x->parent;
while (y != nullptr && x == y->right) {
x = y;
y = y->parent;
}
return y;
}

// find the predecessor of a given node
NodePtr predecessor(NodePtr x) {
// if the left subtree is not null,
// the predecessor is the rightmost node in the
// left subtree
if (x->left != nullptr) {
return maximum(x->left);
}

NodePtr y = x->parent;
while (y != nullptr && x == y->left) {
x = y;
y = y->parent;
}

return y;
}

// insert the key to the tree in its appropriate position
void insert(int key) {
NodePtr node = new Node;
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
node->data = key;
NodePtr y = nullptr;
NodePtr x = this->root;

while (x != nullptr) {
y = x;
if (node->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}

// y is parent of x
node->parent = y;
if (y == nullptr) {
root = node;
} else if (node->data < y->data) {
y->left = node;
} else {
y->right = node;
}
}

NodePtr getRoot(){
return this->root;
}

// delete the node from the tree
NodePtr deleteNode(int data) {
return deleteNodeHelper(this->root, data);
}

// print the tree structure on the screen
void prettyPrint() {
printHelper(this->root, "", true);
}

};

int main() {
BST bst;
bst.createSampleTree1();
bst.prettyPrint();
return 0;
}
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
// Binary search tree implementation in Java
// Author: AlgorithmTutor

// data structure that represents a node in the tree
class Node {
int data; // holds the key
Node parent; // pointer to the parent
Node left; // pointer to left child
Node right; // pointer to right child

public Node(int data) {
this.data = data;
this.parent = null;
this.left = null;
this.right = null;
}
}

public class BST {
private Node root;

public BST() {
root = null;
}

public void createSampleTree1() {
Node node50 = new Node(50);
Node node30 = new Node(30);
Node node70 = new Node(70);

node30.parent = node50;
node70.parent = node50;
node50.left = node30;
node50.right = node70;

Node node23 = new Node(23);
Node node35 = new Node(35);

node23.parent = node30;
node35.parent = node30;
node30.left = node23;
node30.right = node35;

Node node11 = new Node(11);
Node node25 = new Node(25);

node11.parent = node23;
node25.parent = node23;
node23.left = node11;
node23.right = node25;

Node node31 = new Node(31);
Node node42 = new Node(42);

node31.parent = node35;
node42.parent = node35;
node35.left = node31;
node35.right = node42;

Node node80 = new Node(80);

node80.parent = node70;
node70.right = node80;

Node node73 = new Node(73);
Node node85 = new Node(85);

node73.parent = node80;
node85.parent = node80;
node80.left = node73;
node80.right = node85;

this.root = node50;
}

private void printHelper(Node currPtr, String indent, boolean last) {
// print the tree structure on the screen
if (currPtr != null) {
System.out.print(indent);
if (last) {
System.out.print("R----");
indent += " ";
} else {
System.out.print("L----");
indent += "| ";
}

System.out.println(currPtr.data);

printHelper(currPtr.left, indent, false);
printHelper(currPtr.right, indent, true);
}
}

private Node searchTreeHelper(Node node, int key) {
if (node == null || key == node.data) {
return node;
}

if (key < node.data) {
return searchTreeHelper(node.left, key);
}
return searchTreeHelper(node.right, key);
}

private Node deleteNodeHelper(Node node, int key) {
// search the key
if (node == null) return node;
else if (key < node.data) node.left = deleteNodeHelper(node.left, key);
else if (key > node.data) node.right = deleteNodeHelper(node.right, key);
else {
// the key has been found, now delete it

// case 1: node is a leaf node
if (node.left == null && node.right == null) {
node = null;
}

// case 2: node has only one child
else if (node.left == null) {
Node temp = node;
node = node.right;
}

else if (node.right == null) {
Node temp = node;
node = node.left;
}

// case 3: has both children
else {
Node temp = minimum(node.right);
node.data = temp.data;
node.right = deleteNodeHelper(node.right, temp.data);
}

}
return node;
}

private void preOrderHelper(Node node) {
if (node != null) {
System.out.print(node.data + " ");
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}

private void inOrderHelper(Node node) {
if (node != null) {
inOrderHelper(node.left);
System.out.print(node.data + " ");
inOrderHelper(node.right);
}
}

private void postOrderHelper(Node node) {
if (node != null) {
postOrderHelper(node.left);
postOrderHelper(node.right);
System.out.print(node.data + " ");
}
}

// Pre-Order traversal
// Node->Left Subtree->Right Subtree
public void preorder() {
preOrderHelper(this.root);
}

// In-Order traversal
// Left Subtree -> Node -> Right Subtree
public void inorder() {
inOrderHelper(this.root);
}

// Post-Order traversal
// Left Subtree -> Right Subtree -> Node
public void postorder() {
postOrderHelper(this.root);
}

// search the tree for the key k
// and return the corresponding node
public Node searchTree(int k) {
return searchTreeHelper(this.root, k);
}

// find the node with the minimum key
public Node minimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}

// find the node with the maximum key
public Node maximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}

// find the successor of a given node
public Node successor(Node x) {
// if the right subtree is not null,
// the successor is the leftmost node in the
// right subtree
if (x.right != null) {
return minimum(x.right);
}

// else it is the lowest ancestor of x whose
// left child is also an ancestor of x.
Node y = x.parent;
while (y != null && x == y.right) {
x = y;
y = y.parent;
}
return y;
}

// find the predecessor of a given node
public Node predecessor(Node x) {
// if the left subtree is not null,
// the predecessor is the rightmost node in the
// left subtree
if (x.left != null) {
return maximum(x.left);
}

Node y = x.parent;
while (y != null && x == y.left) {
x = y;
y = y.parent;
}

return y;
}

// insert the key to the tree in its appropriate position
public void insert(int key) {
Node node = new Node(key);
Node y = null;
Node x = this.root;

while (x != null) {
y = x;
if (node.data < x.data) {
x = x.left;
} else {
x = x.right;
}
}

// y is parent of x
node.parent = y;
if (y == null) {
root = node;
} else if (node.data < y.data) {
y.left = node;
} else {
y.right = node;
}
}

// delete the node from the tree
Node deleteNode(int data) {
return deleteNodeHelper(this.root, data);
}

// print the tree structure on the screen
public void prettyPrint() {
printHelper(this.root, "", true);
}

public static void main(String [] args) {
BST tree = new BST();
tree.createSampleTree1();
Node n = tree.deleteNode(35);
tree.prettyPrint();
}
}
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
# Binary search tree implementation in Java
# Author: AlgorithmTutor

# data structure that represents a node in the tree

import sys

class Node:
def __init__(self, data):
self.data = data
self.parent = None
self.left = None
self.right = None

class BST:

def __init__(self):
self.root = None

def createSampleTree1(self):
node50 = Node(50)
node30 = Node(30)
node70 = Node(70)

node30.parent = node50
node70.parent = node50
node50.left = node30
node50.right = node70

node23 = Node(23)
node35 = Node(35)

node23.parent = node30
node35.parent = node30
node30.left = node23
node30.right = node35

node11 = Node(11)
node25 = Node(25)

node11.parent = node23
node25.parent = node23
node23.left = node11
node23.right = node25

node31 = Node(31)
node42 = Node(42)

node31.parent = node35
node42.parent = node35
node35.left = node31
node35.right = node42

node80 = Node(80)

node80.parent = node70
node70.right = node80

node73 = Node(73)
node85 = Node(85)

node73.parent = node80
node85.parent = node80
node80.left = node73
node80.right = node85

self.root = node50

def __printHelper(self, currPtr, indent, last):
# print the tree structure on the screen
if currPtr != None:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent += " "
else:
sys.stdout.write("L----")
indent += "| "

print currPtr.data

self.__printHelper(currPtr.left, indent, False)
self.__printHelper(currPtr.right, indent, True)

def __searchTreeHelper(self, node, key):
if node == None or key == node.data:
return node

if key < node.data:
return self.__searchTreeHelper(node.left, key)
return self.__searchTreeHelper(node.right, key)

def __deleteNodeHelper(self, node, key):
# search the key
if node == None:
return node
elif key < node.data:
node.left = self.__deleteNodeHelper(node.left, key)
elif key > node.data:
node.right = self.__deleteNodeHelper(node.right, key)
else:
# the key has been found, now delete it

# case 1: node is a leaf node
if node.left == None and node.right == None:
node = None

# case 2: node has only one child
elif node.left == None:
temp = node
node = node.right

elif node.right == None:
temp = node
node = node.left

# case 3: has both children
else:
temp = minimum(node.right)
node.data = temp.data
node.right = self.__deleteNodeHelper(node.right, temp.data)
return node

def __preOrderHelper(self, node):
if node != None:
sys.stdout.write(node.data + " ")
self.__preOrderHelper(node.left)
self.__preOrderHelper(node.right)

def __inOrderHelper(self, node):
if node != None:
self.__inOrderHelper(node.left)
sys.stdout.write(node.data + " ")
self.__inOrderHelper(node.right)

def __postOrderHelper(self, node):
if node != None:
self.__postOrderHelper(node.left)
self.__postOrderHelper(node.right)
std.out.write(node.data + " ")

# Pre-Order traversal
# Node->Left Subtree->Right Subtree
def preorder(self):
self.__preOrderHelper(self.root)

# In-Order traversal
# Left Subtree -> Node -> Right Subtree
def __inorder(self):
self.__inOrderHelper(self.root)

# Post-Order traversal
# Left Subtree -> Right Subtree -> Node
def __postorder(self):
self.__postOrderHelper(self.root)

# search the tree for the key k
# and return the corresponding node
def searchTree(self, k):
return self.__searchTreeHelper(self.root, k)

# find the node with the minimum key
def minimum(self, node):
while node.left != None:
node = node.left
return node

# find the node with the maximum key
def maximum(self, node):
while node.right != None:
node = node.right
return node

# find the successor of a given node
def successor(self, x):
# if the right subtree is not null,
# the successor is the leftmost node in the
# right subtree
if x.right != None:
return self.minimum(x.right)

# else it is the lowest ancestor of x whose
# left child is also an ancestor of x.
y = x.parent
while y != None and x == y.right:
x = y
y = y.parent
return y

# find the predecessor of a given node
def predecessor(self, x):
# if the left subtree is not null,
# the predecessor is the rightmost node in the
# left subtree
if x.left != None:
return self.maximum(x.left)

y = x.parent
while y != None and x == y.left:
x = y
y = y.parent
return y

# insert the key to the tree in its appropriate position
def insert(self, key):
node = Node(key)
y = None
x = self.root

while x != None:
y = x
if node.data < x.data:
x = x.left
else:
x = x.right

# y is parent of x
node.parent = y
if y == None:
root = node
elif node.data < y.data:
y.left = node
else:
y.right = node

# delete the node from the tree
def deleteNode(self, data):
return self.__deleteNodeHelper(self.root, data)

# print the tree structure on the screen
def prettyPrint(self):
self.__printHelper(self.root, "", True)

if __name__ == '__main__':
tree = BST()
tree.createSampleTree1()
tree.prettyPrint()