###
**What is binary search trees? How to implement in C++?**

This article explains the concept of binary search trees (BST) and provides a sample implementation in C++.

- Binary Search Tree (BST) is a binary tree (has atmost 2 children).
- It is also referred as sorted/ ordered binary tree.
- BST has the following properties. (notes from wikipedia)
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.

- BST Operations:-
- Searching in a BST
- Examine the root node. If tree is NULL value doesn't exist.
- If value equals the key in root search is successful and return.
- If value is less than root, search the left sub-tree.
- If value is greater than root, search the right sub-tree.
- Continue until the value is found or the sub tree is NULL.
- Time complexity. Average: O(log n), Worst: O(n) if the BST is unbalanced and resembles a linked list.

- Insertion in BST
- Insertion begin as a search.
- Compare the key with root. If not equal search the left or right sub tre
- When a leaf node is reached add the new node to left or right based on the value.
- Time complexity. Average: O(log n), Worst O(n)

- Deletion in BST
- There are three possible cases to consider:
- Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
- Deleting a node with one child: Remove the node and replace it with its child.
- Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

### A sample implementation of BST using C++

```
#include <iostream>
using namespace std;
// A generic tree node class
class Node {
int key;
Node* left;
Node* right;
Node* parent;
public:
Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
void setKey(int aKey) { key = aKey; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
void setParent(Node* aParent) { parent = aParent; };
int Key() { return key; };
Node* Left() { return left; };
Node* Right() { return right; };
Node* Parent() { return parent; };
};
// Binary Search Tree class
class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
void addNode(int key);
Node* findNode(int key, Node* parent);
void walk(Node* node);
void deleteNode(int key);
Node* min(Node* node);
Node* max(Node* node);
Node* successor(int key, Node* parent);
Node* predecessor(int key, Node* parent);
private:
void addNode(int key, Node* leaf);
void freeNode(Node* leaf);
};
// Constructor
Tree::Tree() {
root = NULL;
}
// Destructor
Tree::~Tree() {
freeNode(root);
}
// Free the node
void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}
// Add a node [O(height of tree) on average]
void Tree::addNode(int key)
{
// No elements. Add the root
if ( root == NULL ) {
cout << "add root node ... " << key << endl;
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
cout << "add other node ... " << key << endl;
addNode(key, root);
}
}
// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() )
{
if ( leaf->Left() != NULL )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setLeft(n);
}
}
else
{
if ( leaf->Right() != NULL )
addNode(key, leaf->Right());
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setRight(n);
}
}
}
// Find a node [O(height of tree) on average]
Node* Tree::findNode(int key, Node* node)
{
if ( node == NULL )
return NULL;
else if ( node->Key() == key )
return node;
else if ( key <= node->Key() )
findNode(key, node->Left());
else if ( key > node->Key() )
findNode(key, node->Right());
else
return NULL;
}
// Print the tree
void Tree::walk(Node* node)
{
if ( node )
{
cout << node->Key() << " ";
walk(node->Left());
walk(node->Right());
}
}
// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
if ( node == NULL )
return NULL;
if ( node->Left() )
min(node->Left());
else
return node;
}
// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
if ( node == NULL )
return NULL;
if ( node->Right() )
max(node->Right());
else
return node;
}
// Find successor to a node
// Find the node, get the node with max value
// for the right sub-tree to get the successor
Node* Tree::successor(int key, Node *node)
{
Node* thisKey = findNode(key, node);
if ( thisKey )
return max(thisKey->Right());
}
// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-tree to get the predecessor
Node* Tree::predecessor(int key, Node *node)
{
Node* thisKey = findNode(key, node);
if ( thisKey )
return max(thisKey->Left());
}
// Delete a node
// (1) If leaf just delete
// (2) If only one child delete this node and replace
// with the child
// (3) If 2 children. Find the predecessor (or successor).
// Delete the predecessor (or successor). Replace the
// node to be deleted with the predecessor (or successor).
void Tree::deleteNode(int key)
{
// Find the node.
Node* thisKey = findNode(key, root);
// (1)
if ( thisKey->Left() == NULL && thisKey->Right() == NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(NULL);
else
thisKey->Parent()->setLeft(NULL);
delete thisKey;
}
// (2)
if ( thisKey->Left() == NULL && thisKey->Right() != NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(thisKey->Right());
else
thisKey->Parent()->setLeft(thisKey->Right());
delete thisKey;
}
if ( thisKey->Left() != NULL && thisKey->Right() == NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(thisKey->Left());
else
thisKey->Parent()->setLeft(thisKey->Left());
delete thisKey;
}
// (3)
if ( thisKey->Left() != NULL && thisKey->Right() != NULL )
{
Node* sub = predecessor(thisKey->Key(), thisKey);
if ( sub == NULL )
sub = successor(thisKey->Key(), thisKey);
if ( sub->Parent()->Key() <= sub->Key() )
sub->Parent()->setRight(sub->Right());
else
sub->Parent()->setLeft(sub->Left());
thisKey->setKey(sub->Key());
delete sub;
}
}
// Test main program
int main() {
Tree* tree = new Tree();
// Add nodes
tree->addNode(300);
tree->addNode(100);
tree->addNode(200);
tree->addNode(400);
tree->addNode(500);
// Traverse the tree
tree->walk(tree->Root());
cout << endl;
// Find nodes
if ( tree->findNode(500, tree->Root()) )
cout << "Node 500 found" << endl;
else
cout << "Node 500 not found" << endl;
if ( tree->findNode(600, tree->Root()) )
cout << "Node 600 found" << endl;
else
cout << "Node 600 not found" << endl;
// Min & Max
cout << "Min=" << tree->min(tree->Root())->Key() << endl;
cout << "Max=" << tree->max(tree->Root())->Key() << endl;
// Successor and Predecessor
cout << "Successor to 300=" <<
tree->successor(300, tree->Root())->Key() << endl;
cout << "Predecessor to 300=" <<
tree->predecessor(300, tree->Root())->Key() << endl;
// Delete a node
tree->deleteNode(300);
// Traverse the tree
tree->walk(tree->Root());
cout << endl;
delete tree;
return 0;
}
```

OUTPUT:- add root node ... 300 add other node ... 100 add other node ... 200 add other node ... 400 add other node ... 500 300 100 200 400 500 Node 500 found Node 600 not found Min=100 Max=500 Successor to 300=500 Predecessor to 300=200 200 100 400

Your implementation of sucessor is wrong. For example, what if a node doesn't have a right child? In this case, its successor would be in its ancestors. Same error for the implementation of predecessor.

ReplyDeleteFrom void Tree::deleteNode(int key)

ReplyDeleteI have a question regarding part 1 of the above said function.

Considering my B-Tree only has 1 node. won't this line give me error during compilation.

if ( thisKey->Key() > thisKey->Parent()->Key() )

As Node* thisKey = findNode(key, root); will set thisKey = root.

And you are not setting any parent in this case. like, a root is a parent of it self. your addNode does not specify it anywhere.

thisKey->Parent()->Key() might give an error.

In the function "findNode" you have forgotten the statement "return" before findNode(key, node->Left()); and findNode(key, node->Right());

ReplyDeleteYour implementation of successor is wrong. For example, what if a node doesn't have a right child? In this case, its successor would be in its ancestors.moreover,even if node x has right child ,successor of node x is leftmost node of x's right sub-tree

ReplyDeleteso your function should be:

Node* Tree::successor(int key, Node *node)

{

Node* thisKey = findNode(key, node);

if ( thisKey )

return min(thisKey->Right());

}

I never understood BST.. you provided very detailed tutorial Thanks

ReplyDeleteBinary search trees and implementation is well explained. Thanks for that. You can find more here below.

ReplyDeleteImplementation of the Binary tree in Cpp working code and tests