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.
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.
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.
Operation
Average Case
Worst Case
1
Search
O(log n)
O(n)
2
Minimum
O(log n)
O(n)
3
Maximum
O(log n)
O(n)
4
Predecessor
O(log n)
O(n)
5
Successor
O(log n)
O(n)
6
Insert
O(log n)
O(n)
7
Delete
O(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.
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.
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.
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.
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.
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.
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.
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.
We copy the minimum node y of x’s right subtree and place it in the place of x.
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.
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.
// Binary search tree implementation in C++ // Author: Algorithm Tutor
#include
usingnamespacestd;
// data structure that represents a node in the tree structNode { 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 classBST { private: NodePtr root;
// initializes the nodes with appropirate values // all the pointers are set to point to the null pointer voidinitializeNode(NodePtr node, int key){ node->data = key; node->parent = nullptr; node->left = nullptr; node->right = nullptr; }
// case 3: has both children else { NodePtr temp = minimum(node->right); node->data = temp->data; node->right = deleteNodeHelper(node->right, temp->data); }
} return node; }
voidprintHelper(NodePtr root, string indent, bool last){ // print the tree structure on the screen if (root != nullptr) { cout< if (last) { cout<<"└────"; indent += " "; } else { cout<<"├────"; indent += "| "; }
// In-Order traversal // Left Subtree -> Node -> Right Subtree voidinorder(){ inOrderHelper(this->root); }
// Post-Order traversal // Left Subtree -> Right Subtree -> Node voidpostorder(){ 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 voidinsert(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; } elseif (node->data < y->data) { y->left = node; } else { y->right = node; } }
NodePtr getRoot(){ returnthis->root; }
// delete the node from the tree NodePtr deleteNode(int data){ return deleteNodeHelper(this->root, data); }
// print the tree structure on the screen voidprettyPrint(){ printHelper(this->root, "", true); }
// Binary search tree implementation in Java // Author: AlgorithmTutor
// data structure that represents a node in the tree classNode{ int data; // holds the key Node parent; // pointer to the parent Node left; // pointer to left child Node right; // pointer to right child
// In-Order traversal // Left Subtree -> Node -> Right Subtree publicvoidinorder(){ inOrderHelper(this.root); }
// Post-Order traversal // Left Subtree -> Right Subtree -> Node publicvoidpostorder(){ 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 publicvoidinsert(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; } elseif (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 publicvoidprettyPrint(){ printHelper(this.root, "", true); }
publicstaticvoidmain(String [] args){ BST tree = new BST(); tree.createSampleTree1(); Node n = tree.deleteNode(35); tree.prettyPrint(); } }
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 += "| "
# case 3: has both children else: temp = minimum(node.right) node.data = temp.data node.right = self.__deleteNodeHelper(node.right, temp.data) return node
# 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 defsearchTree(self, k): return self.__searchTreeHelper(self.root, k)
# find the node with the minimum key defminimum(self, node): while node.left != None: node = node.left return node
# find the node with the maximum key defmaximum(self, node): while node.right != None: node = node.right return node
# find the successor of a given node defsuccessor(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 != Noneand x == y.right: x = y y = y.parent return y
# find the predecessor of a given node defpredecessor(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 != Noneand x == y.left: x = y y = y.parent return y
# insert the key to the tree in its appropriate position definsert(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 defdeleteNode(self, data): return self.__deleteNodeHelper(self.root, data)
# print the tree structure on the screen defprettyPrint(self): self.__printHelper(self.root, "", True)
if __name__ == '__main__': tree = BST() tree.createSampleTree1() tree.prettyPrint()