CS-2001
Data Structures
Fall 2023
Binary Search Tree Implementation
Mr. Muhammad Usman Joyia
National University of Computer and
Emerging Sciences,
Faisalabad, Pakistan.
Binary Search Tree (BST)
• With a binary tree, we can dictate an order on the two children
• Binary Search Tree (BST) defines the following order:
– All elements in the left sub-tree to be less than the element stored in
the root node, and
– All elements in the right sub-tree to be greater than the element in the
root object
subtrees will
themselves be
binary search trees
2
Binary Search Tree (BST) – Example (1)
3
Binary Search Tree (BST) – Example (2)
10
2 45 10
5 30
5 45
30
2 25 45
10 2 25 30
BST
25 Not BST
BST
4
BST Operations
• Many operations one can perform on a binary search tree
– Creating a binary search tree
– Finding a node in a binary search tree
– Inserting a node into a binary search tree
– Deleting a node in a binary search tree
– Traversing a binary search tree
• In the following, we will examine the algorithms and examples for
all of the above operations
5
Creating BST
• A simple class that implements a binary tree to store integer values
– A class called IntBinaryTree
• Node of binary search tree
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
};
6
Creating BST – Class Definition
class IntBinaryTree {
private:
TreeNode *root; // Pointer to the root of BST
void destroySubTree(TreeNode *); //Recursively delete all tree nodes
void deleteNode(int, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *);
void displayPreOrder(TreeNode *);
void displayPostOrder(TreeNode *);
public:
IntBinaryTree() { root = NULL; }
~IntBinaryTree() { destroySubTree(root); }
void insertNode(int);
bool find(int);
void remove(int);
void showNodesInOrder() { displayInOrder(root); }
void showNodesPreOrder() { displayPreOrder(root); }
void showNodesPostOrder() { displayPostOrder(root); }
};
7
Finding a Node in BST
• Recall that a BST has the following key property (invariant):
– Smaller values in left sub-tree
– Larger values in right sub-tree
• For example: find (81)
– Returns true if found
8
Finding a Node in BST
• Recall that a BST has the following key property (invariant):
– Smaller values in left sub-tree
– Larger values in right sub-tree
• For example: find (36)
– Returns false if not found
9
Finding a Node in BST
• Example: find(2)
root
10
10 > 2, left
5 30 5 > 2, left
2 = 2, found
2 25 45
10
Finding a Node in BST
• Example: find(25)
root
5
5 < 25, right
2 45
45 > 25, left
30 > 25, left
30
10 < 25, right
10 25 = 25, found
25
11
Finding a Node in BST – Implementation
bool IntBinaryTree::Find(int num){
// The function starts from the root
TreeNode *nodePtr = root;
while (nodePtr) {
if (nodePtr->value == num)
return true; // value is found
else if (num < nodePtr->value)
nodePtr = nodePtr->left;
else
10 10 < 25, right
nodePtr = nodePtr->right;
}
return false; // value not found 5 30 30 > 25, left
}
25 = 25, found
2 25 45
12
Inserting a Node in BST
• An insertion will be performed as a leaf node
– Any empty node is a possible location for an insertion
• Values which may be inserted at any empty node depend on the
surrounding nodes
13
Inserting a Node in BST
• Which values can be held by empty node?
This node may hold
48, 49, or 50
14
Inserting a Node in BST
• Which values can be held by empty node?
This node may hold
35, 36, 37 or 38
15
Inserting a Node in BST – Algorithm
• Like find, algorithm will step through the tree
– If algorithm find the object already in the tree, it will return
The object is already in the binary search tree (no duplicates)
– Otherwise, algorithm will arrive at an empty node
– The object will be inserted into that location
16
Inserting a Node in BST – Example
• insertNode(20)
10
10 < 20, right
5 30
30 > 20, left
25 > 20, left
2 25 45
Insert 20 on left
20
17
Inserting a Node in BST – Implementation
void IntBinaryTree::insertNode(int num) {
TreeNode* newNode = new TreeNode; // Create a new node
newNode->value = num;
newNode->left = newNode->right = NULL;
if (!root) root = newNode; // If tree is empty.
else { // Tree is not empty
TreeNode* nodePtr = root; // create a pointer to traverse the tree
while ( true ) {
if (num < nodePtr->value) { // Left subtree
if (nodePtr->left!=NULL) { nodePtr = nodePtr->left; }
else { nodePtr->left = newNode; return; }
}
else if (num > nodePtr->value) { // Right subtree
if (nodePtr->right !=NULL) {nodePtr = nodePtr->right;}
else { nodePtr->right = newNode; return; }
}
else { cout << "Duplicate value found in tree.\n"; break; }
}
}
} 18
Inserting a Node in BST – Observation (1)
• Insertion may unbalance the tree
• It is possible to have a degenerate BST
– The example is equivalent to a linked list
19
Inserting a Node in BST – Observation (2)
• All these binary search trees store the same data
– Resultant tree depends on the order in which the values are inserted
20
Using BST (1)
// This program builds a binary tree with 5 nodes.
#include <iostream.h>
#include "IntBinaryTree.h“
Output:
void main(void)
Inserting nodes.
{ 3 is found in the tree.
IntBinaryTree tree;
cout << "Inserting nodes.\n";
[Link](5);
[Link](8);
[Link](3);
[Link](12);
[Link](9);
if ([Link](3))
cout << "3 is found in the tree.\n";
else
cout << "3 was not found in the tree.\n";
}
21
Using BST (2)
• Structure of binary tree built by the program
22
Deleting a Node
• A node being erased is not always going to be a leaf node
• There are three possible scenarios:
– The node is a leaf node,
– It has exactly one child, or
– It has two children (it is a full node)
23
Deleting a Node – Leaf Node
• Deleting a leaf node is easy
– Find its parent
– Set the child pointer that links it with parent to NULL
– Free the node’s memory
• Consider deleting node containing 25
10 10
10 < 25, right
5 30 30 > 25, left 5 30
25 = 25, delete
2 25 45 2 45
24
Deleting a Node – Leaf Node
• Consider deleting node containing 75
25
Deleting a Node – Leaf Node
• Consider deleting node containing 75
– The node is deleted and left child of 81 is set to NULL
26
Deleting a Node – Leaf Node
• Consider deleting node containing 40
27
Deleting a Node – Leaf Node
• Consider deleting node containing 40
– Node is deleted and right child of 39 is set to NULL
28
Deleting a Node – Node With Child
• If a node has only one child (left or right)
– Simply promote the subtree associated with the child
• Consider deleting 18 which has one right child
– Node 18 is deleted and right tree of node 5 is updated to point to 21
29
Deleting a Node – Node With Child
• Consider deleting 8 which has one left child
30
Deleting a Node – Node With Child
• Consider deleting 8 which has one left child
– Node 8 is deleted and the left tree of 11 is updated to point to 3
31
Deleting a Node – Node With Child
• Consider deleting the node containing 99
32
Deleting a Node – Node With Child
• Consider deleting the node containing 99
– The right tree of 70 is set to point to node 92
– Again, the order of the tree is maintained
33
Deleting a Node – Node With Two Children
• The problem is not as easily solved if the node has two children
34
Deleting a Node – Node With Two Children
• Suppose node p with two children has to be deleted
– Find a position in the right subtree of p to attach its left subtree
Left most node in the right subtree of node p (successor of p )
– Attach the right subtree of node p to its parent
• Consider deleting 10
10
30
30
10
25 45
25 45
5 30
5
5 Attach left
Attach right
subtree of
2 25 45 10 to that subtree of
node, i.e., 25
2 10 to its
Find left most node of 2 parent
right subtree of 10 35
Pointers Review
• Pointer to Pointer versus reference to Pointer?
int g_One=1; int g_One=1;
void func(int* pInt); void func(int*& rpInt);
int main() int main()
{ {
int nvar=2; int nvar=2;
int* pvar=&nvar; int* pvar=&nvar;
func(pvar); func(pvar);
std::cout<<*pvar<<std::endl; std::cout<<*pvar<<std::endl;
return 0; return 0;
} }
void func(int* pInt) void func(int*& rpInt)
{ {
pInt=&g_One; rpInt=&g_One;
} }
36
Deleting a Node – Implementation
class IntBinaryTree {
private:
TreeNode *root; // Pointer to the root of BST
void destroySubTree(TreeNode *); //Recursively delete all tree nodes
void deleteNode(int, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *);
void displayPreOrder(TreeNode *); The argument passed to the
void displayPostOrder(TreeNode *); remove function is the value of
the node to be deleted.
public:
IntBinaryTree() { root = NULL; }
~IntBinaryTree() { destroySubTree(root); }
void insertNode(int);
bool find(int);
void remove(int num); { deleteNode( num, root)}
void showNodesInOrder() { displayInOrder(root); }
void showNodesPreOrder() { displayPreOrder(root); }
void showNodesPostOrder() { displayPostOrder(root); }
};
37
Deleting a Node – Implementation
void IntBinaryTree::deleteNode(int num, TreeNode *&nodePtr)
{
if (nodePtr == NULL) // node does not exist in the tree
cout << num <<“ not found.\n";
else if (num < nodePtr->value)
deleteNode(num, nodePtr->left); // find in left subtree
else if (num > nodePtr->value)
deleteNode(num, nodePtr->right); // find in right subtree
else // num == nodePtr->value i.e. node is found
makeDeletion(nodePtr); // actually deletes node from BST
}
Note:
• The declaration of the nodePtr parameter: TreeNode *&nodePtr;
• nodePtr is a reference to a pointer to a TreeNode structure
– Any action performed on nodePtr is actually performed on the argument
passed into nodePtr 38
Deleting a Node – Implementation
void IntBinaryTree::makeDeletion(TreeNode *&nodePtr) {
TreeNode *tempNodePtr; // Temperary pointer
if (nodePtr->right == NULL) { // case for leaf and one (left) child
tempNodePtr = nodePtr;
nodePtr = nodePtr->left; // Reattach the left child
delete tempNodePtr;
}
else if (nodePtr->left == NULL) { // case for one (right) child
tempNodePtr = nodePtr;
nodePtr = nodePtr->right; // Reattach the right child
delete tempNodePtr;
}
else { // case for two children.
tempNodePtr = nodePtr->right; // Move one node to the right
while (tempNodePtr->left) { // Go to the extreme left node
tempNodePtr = tempNodePtr->left;
}
tempNodePtr->left = nodePtr->left; // Reattach the left subtree
tempNodePtr = nodePtr;
nodePtr = nodePtr->right; // Reattach the right subtree
delete tempNodePtr;
} 39
}
Deleting a Node – Node With Two Children
• Problem: Height of the BST increases
• A better Solution to delete node p with two children
– Replace node p with the minimum object in the right subtree
– Delete that object from the right subtree
40
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 42
41
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 42
– Find minimum object in the right subtree, i.e., 47
42
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 42
– Find minimum object in the right subtree, i.e., 47
– Replace 42 with 47
43
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 42
– Find minimum object in the right subtree, i.e., 47
– Replace 42 with 47
– Delete the leaf node 47
44
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 47
45
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 47
– Replace 47 with 51
46
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 47
– Replace 47 with 51
– Node 51 is not a leaf node
47
Deleting a Node Two Children – Better Solution
• Consider the problem of deleting a full node, e.g., 47
– Replace 47 with 51
– Node 51 is not a leaf node
Assign the left subtree of 70 to point to 59
48
Using BST
// This program builds a binary tree with 5 nodes.
// The DeleteNode function is used to remove two of them.
#include <iostream.h>
#include "IntBinaryTree.h“ Program Output:
void main(void) {
Inserting nodes.
IntBinaryTree tree; Here are the values in
the tree:
cout << "Inserting nodes.\n"; 3
[Link](5);
[Link](8); 5
[Link](3); 8
[Link](12); 9
[Link](9);
12
cout << "Here are the values in the tree:\n";
[Link]();
cout << "Deleting 8...\n";
[Link](8);
cout << "Deleting 12...\n";
[Link](12);
cout << "Now, here are the nodes:\n";
[Link]();
}
49
Using BST
// This program builds a binary tree with 5 nodes.
// The DeleteNode function is used to remove two of them.
#include <iostream.h>
#include "IntBinaryTree.h“ Program Output:
Inserting nodes.
void main(void) {
IntBinaryTree tree; Here are the values in
the tree:
cout << "Inserting nodes.\n"; 3
[Link](5);
[Link](8);
5
[Link](3); 8
[Link](12); 9
[Link](9); 12
cout << "Here are the values in the tree:\n"; Deleting 8...
[Link](); Deleting 12...
cout << "Deleting 8...\n"; Now, here are the
[Link](8); nodes:
cout << "Deleting 12...\n";
[Link](12); 3
5
cout << "Now, here are the nodes:\n"; 9
[Link]();
}
50
Traversing a Binary Search Tree
class IntBinaryTree {
private:
TreeNode *root; // Pointer to the root of BST
void destroySubTree(TreeNode *); //Recursively delete all tree nodes
void deleteNode(int, TreeNode *&);
void makeDeletion(TreeNode *&);
Recursive implementation as
void displayInOrder(TreeNode *);
void displayPreOrder(TreeNode *); discussed in the slides of Tree
void displayPostOrder(TreeNode *); Traversal chapter.
public:
IntBinaryTree() { root = NULL; }
~IntBinaryTree() { destroySubTree(root); }
void insertNode(int);
bool find(int);
void remove(int);
void showNodesInOrder() { displayInOrder(root); }
void showNodesPreOrder() { displayPreOrder(root); }
void showNodesPostOrder() { displayPostOrder(root); }
};
51
Program output:
Using BST Inserting nodes.
Inorder traversal:
// This program builds a binary tree with 5 nodes. 3
// The nodes are displayed with inorder, preorder, and 5 algorithms.
postorder
#include <iostream.h> 8
#include "IntBinaryTree.h“
9
void main(void) 12
{
IntBinaryTree tree;
Preorder traversal:
cout << "Inserting nodes.\n"; 5
[Link](5); 3
[Link](8); 8
[Link](3);
[Link](12); 12
[Link](9); 9
cout << "Inorder traversal:\n";
[Link]();
Postorder traversal:
cout << "\nPreorder traversal:\n"; 3
[Link]();
9
cout << "\nPostorder traversal:\n";
[Link](); 12
} 8
5
52
Any Question So Far?
53
