Data structure - Binary Search Tree

Binary Search Trees are Binary trees that have the following properties:

  1. At most 2 child nodes per node.
  2. Any nodes on the left are less than the parent node (including sub-tree).
  3. Any node on the right are greater than the parent node (including sub-tree).

Inserting / Building BST

The BST properties must be maintain BST properties even when inserting a node into a BST. There are two cases to handle when inserting a node in BST:

  1. Inserting a node at root (root = null).
  2. Inserting into a node that has child nodes.

Inserting a node into the root involves creating a new node and assign it to the root. All subsequent node insertions will start from this root. When inserting into a node with childeren we have to evaluate all its child nodes until we reach a leaf. We place the node left or right depending on if the node value is less or greater than the value we are inserting (respectively).

Binary Sarch Tree example, Showing insertion of 61, left and 63, right.

Searching BST

The BST data structure references the root node. From the root node of a BST we can traverse the tree of nodes and reach any child node in the tree. Using the BST shown above when we try to locate 72 we do the following:

  1. Start with root.
  2. If node has childeren, evaluate:
    if node.value < 72, advance to right node (where bigger node.value would be located)
    if node.value > 72, advance to left node (where smaller node.value would be located)
  3. Traverse all the way to leaf until node.value is found.

Below diagram depicts the above steps to locate the value of 72.

Binary Sarch Tree example, left shows example of a BST, right shows traversing tree to find value 72.

Deleting a node

When deleting a node in a tree we need to remove all the references to the node to be deleted. The child nodes in BST do not have a reference to the parent node. This means when deleting a node we need to be operate on the parent node.

There are 3 cases to consider:

  1. Deleting a node at the leaf
    BTS deleting a leaf node.
  2. Deleting a node with childerem
    BTS deleting node with 1 child (node with no childeren).
  3. Deleting a node that is the parent of 2 child nodes.
    BTS deleting node with 2 child nodes along with a sub-case.

Finding Min/Max

operation description
min left most node in a BST
max right most node in a BST

BST - Code example

Below shows code to build BST using recursion:

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
const treeNode = (initValue) => {
return {
nodeValue: initValue,
left: null,
right: null,
insert(value) {
if (this.nodeValue >= value) {
if (this.left) {
this.left.insert(value);
} else {
this.left = treeNode(value);
return;
}
}
else {
// if (nodeValue < value)
if (this.right) {
this.right.insert(value);
} else {
this.right = treeNode(value);
return;
}
}
},
find(value) {
if (this.nodeValue === value) {
return this;
}
else if (this.nodeValue >= value && this.left) {
return this.left.find(value);
}
else if (this.nodeValue < value && this.right) {
return this.right.find(value);
}
},
minNodeForSwap() {
if (this.left) {
return this.left;
}

return this;
},
min() {
if (this.left) {
return this.left.min();
}
return this;
},
max() {
if (this.right) {
return this.right.max();
}
return this;
}
}
}
const BST_Recursion = () => {
return {
rootNode: null,
size: 0,
insert(value) {
if (this.rootNode) {
this.rootNode.insert(value);
}
else {
this.rootNode = treeNode(value);
}
},
find(value) {
if (this.rootNode) {
return this.rootNode.find(value);
}
return null;
},
delete(value) {
let parent = this.rootNode;
let current = this.rootNode;
let isParentsLeft = false;
while (current) {
if (current.nodeValue === value)
break;

parent = current;
if (current.nodeValue >= value) {
current = current.left;
isParentsLeft = true;
} else { // current.nodeValue < value
current = current.right;
isParentsLeft = false;
}
}

if (!current)
return -1;

// found node-to-delete, relative to parent
// check if node-to-delete has left/right childeren
if (current.left && !current.right) {
// left child only...
if (isParentsLeft) // find out left/right to update at parent node
parent.left = current.left;
else
parent.right = current.left;
}
else if (current.right && !current.left) {
// right child only
if (isParentsLeft)
parent.left = current.right;
else
parent.right = current.right;
}
else if (current.left && current.right) {
// left and right child
const smallestOfRightSubTree = current.right.minNodeForSwap();
current.right.left = null;
// if node to swap has right node, assign to current.right's left node else set null
current.right.left = smallestOfRightSubTree.right || null;

if (isParentsLeft) {
smallestOfRightSubTree.left = current.left;
smallestOfRightSubTree.right = current.right;
if (isParentsLeft)
parent.left = smallestOfRightSubTree;
else
parent.right = smallestOfRightSubTree;
}
}
else if (!current.left && !current.right) {
// has left node...
if (isParentsLeft)
parent.left = null;
else
parent.right = null;
}
return parent;
},
min() {
if (this.rootNode) {
return this.rootNode.min();
}
},
max() {
if (this.rootNode) {
return this.rootNode.max();
}
}
}
}
(() => {
const testData = [52, 33, 65, 25, 39, 60, 78, 12, 27, 34, 48, 72, 90, 70];

// const bst_0 = BST_Recursion();
// testData.forEach((value) => bst_0.insert(value));
// console.log(JSON.stringify(bst_0.rootNode, null, 2));

// const bst_1 = BST_Recursion();
// testData.forEach((value) => bst_1.insert(value));
// bst_1.delete(34);
// console.log(JSON.stringify(bst_1.rootNode));

// const bst_2 = BST_Recursion();
// testData.forEach((value) => bst_2.insert(value));
// bst_2.delete(72);
// console.log(JSON.stringify(bst_2.rootNode));

// const bst_3 = BST_Recursion();
// testData.push(36);
// testData.forEach((value) => bst_3.insert(value));
// bst_3.delete(33);
// console.log(JSON.stringify(bst_3.rootNode));

// console.log(bst_3.min());
// console.log(bst_3.max());
})();

BST Traversal

Traversal - in-order

  1. Traverse left subtree (and all its sub-trees)
  2. root
  3. Traverse right subtree (and all its sub-trees)

BTS - In order traversal example.

Traversal - pre-order

  1. root
  2. Traverse left subtree (and all its sub-trees)
  3. Traverse right subtree (and all its sub-trees)

BTS - Pre-order traversal example.

Traversal - post-order

  1. Traverse left subtree (and all its sub-trees)
  2. Traverse right subtree (and all its sub-trees)
  3. root

BTS - Post-order traversal example.

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
const treeNode = (initValue) => {
return {
nodeValue: initValue,
left: null,
right: null,
insert(value) {
if (this.nodeValue >= value) {
if (this.left) {
this.left.insert(value);
} else {
this.left = treeNode(value);
return;
}
}
else {
// if (nodeValue < value)
if (this.right) {
this.right.insert(value);
} else {
this.right = treeNode(value);
return;
}
}
}
}
}
const BST_Recursion = () => {
return {
rootNode: null,
size: 0,
insert(value) {
if (this.rootNode) {
this.rootNode.insert(value);
}
else {
this.rootNode = treeNode(value);
}
},
traverse(type) {
const result = [];
switch (type) {
case 'in-order':
this.inOrder(this.rootNode, result);
break;
case 'pre-order':
this.preOrder(this.rootNode, result);
break;
case 'post-order':
this.postOrder(this.rootNode, result);
break;
}
return result;
},
inOrder(node, result) {
if (node.left) {
this.inOrder(node.left, result);
}
result.push(node.nodeValue);
if (node.right) {
this.inOrder(node.right, result);
}
},
preOrder(node, result) {
result.push(node.nodeValue);
if (node.left) {
this.inOrder(node.left, result);
}
if (node.right) {
this.inOrder(node.right, result);
}
},
postOrder(node, result) {
if (node.left) {
this.inOrder(node.left, result);
}
if (node.right) {
this.inOrder(node.right, result);
}
result.push(node.nodeValue);
}
}
}
(() => {
const testData = [52, 33, 65, 25, 39, 60, 78, 12, 27, 34, 48, 72, 90];
const bst_0 = BST_Recursion();
testData.forEach((value) => bst_0.insert(value));
console.log(bst_0.traverse('in-order'));
console.log(bst_0.traverse('pre-order'));
console.log(bst_0.traverse('post-order'));
})();

Balancing BST

There are technique that can maintain the balance of a tree. For example AVL, Red-Back tree etc…

BST height

Earlier we came across examples where the data and operations can cause a BST to become unbalanced. Un balanaced tree affect the performance of BST operations because the time complexity of the operations are proportional to the height of the BST.

Below we will show that in a balanced BST tree, the height of the BST is logrithmic scale of the total number of nodes:

BST - show that h is O(log(2)n) in a balanced tree.

Time Complexity - BST Operation

Note that we are assuming that the BST is balanced.

operation T(n) Complexity comment
Search O(log(2)n) searching worst case search would be the full height of the tree.
Insertion O(log(2)n) + O(1) searching for the node + pointer changes.
Deletion O(log(2)n) + O(1) searching for the node + pointer changes.
Min O(log(2)n)
Max O(log(2)n)