# Binary search tree (C Plus Plus)

### From LiteratePrograms

**Other implementations**: C |**C++**| Haskell | Java | Scheme | Standard ML

This article implements a simple binary search tree data structure in C++ with search, insert, and delete operations.

## Contents |

## Node structure

We begin by defining a templated node class, which contains left and right child pointers and the node's data. The data is publically accessible but read-only to preserve the order property:

<<node class>>=template<classT>classBSTNode{public: BSTNode method declarations T getData(){returndata;}private: T data; BSTNode<T>* left; BSTNode<T>* right;};

We assume that `T`

implements `operator<`

, which we will need to order the nodes. Constructing nodes is straightforward:

<<BSTNode method declarations>>=BSTNode(T data);<<node constructor>>=template<classT> BSTNode::BSTNode(T data){this->data = data;this->left =this->right = NULL;}

We represent a whole tree with a class that just contains a pointer to the root node, which can be NULL for an empty tree. We make `BSTNode`

a friend class so that the tree can access its internal child pointers but no one else can:

<<tree class>>=template<classT>classBinarySearchTree{public: BinarySearchTree method declarationsprivate: BSTNode<T>* root;friendclassBSTNode<T>;};

## Search

The most important operation on the tree is searching, which uses the properties of the binary search tree to traverse from the root down towards a given node. In the end it will either find the requested node or prove that it is not in the tree, in which case it returns a pointer to NULL. We return the address of the node pointer instead of just the node pointer to facilitate in-place updates.

<<BinarySearchTree method declarations>>=BSTNode<T>** search(T data);<<search operation>>=template<classT> BSTNode<T>** BinarySearchTree<T>::search(T data){BSTNode<T>** node = &root;while(*node != NULL){if(data < (*node)->data) node = &(*node)->left;elseif((*node)->data < data) node = &(*node)->right;elsebreak;}returnnode;}

## Insert

(Warning: This section contains errors!) Inserting is now simple. We search for the node, and if it is not found, we create a new node and put it in the place the search function expected to find it, which is where it belongs in the tree. This particular insertion function does not allow duplicate values in the tree (set semantics), but one that does would be similar.

<<BinarySearchTree method declarations>>=voidinsert(T data);<<insert operation>>=template<classT>voidBinarySearchTree<T>::insert(T data){BSTNode<T>** node = search(data);if(*node == NULL){*node =newBSTNode<T>(data);}}

## Deletion

Deletion is the most complicated operation. We focus on deleting nodes rather than values, since `search()`

can be used to find a node based on a value if necessary. Deleting a node with one child or less is simple; we just replace it with its child:

<<BinarySearchTree method declarations>>=voiddelete_node(BSTNode<T>** node);<<delete operation>>=template<classT>voidBinarySearchTree<T>::delete_node(BSTNode<T>** node){BSTNode<T>* old_node = *node;if((*node)->left == NULL){*node = (*node)->right;deleteold_node;}elseif((*node)->right == NULL){*node = (*node)->left;deleteold_node;}else{delete node with two children}}

A node's *inorder predecessor* is the node whose value immediately precedes the node's value in sorted order. We can find this node by following right child pointers repeatedly starting at the node's left child. Similarly, the *inorder successor* immediately follows it in sorted order, and can be found by following left child pointers starting at the node's right child.

<<find inorder predecessor>>=BSTNode<T>** pred = &(*node)->left;while((*pred)->right != NULL){pred = &(*pred)->right;}

To delete a node with two children, as shown below, we simply exchange the value of the node with either its inorder predecessor or successor, then delete the node that we exchanged with. This preserves the order properties of the tree, and the predecessor/successor nodes always have at most one child, so we already know how to delete them. In this implementation, we choose to consistently use the predecessor.

<<delete node with two children>>=find inorder predecessor std::swap((*pred)->data, (*node)->data); delete_node(pred);

We need a header for `std::swap`

:

<<header files>>=#include <algorithm>

## Files

We can place this implementation in a source and header file for reuse:

<<bst.h>>=#ifndef _BST_H_#define _BST_H_node class tree class#endif<<bst.cpp>>=header files#include "bst.h"search operation insert operation delete operation

This completes the implementation.