Binary Search Trees in C++

Data Structures and Algorithms with C++ is a great course to learn about the various data structures and algorithms used in C++. In this article, we’ll be focusing on Binary Search Trees (BSTs). We’ll discuss how the tree structure works, as well as the time and space complexity associated with access, search, insertion, and deletion.

What Are Binary Search Trees?

Binary Search Trees are a type of tree data structure where each node has up to two children. The left child node always has a lower value than its parent node, while the right child node always has a higher value. The root node of the tree is the topmost node, and is usually the highest or lowest value node in the entire tree.

The structure of a Binary Search Tree makes it easy to quickly access, search, insert, and delete nodes. This makes it a great choice for applications where fast access and manipulation of data is needed.

Time Complexity in Binary Search Trees

Time complexity refers to the amount of time it takes to access, search, insert, or delete nodes in a tree. The time complexity of these operations in a Binary Search Tree depends on the size of the tree.

Access

Accessing a single node in a Binary Search Tree has a time complexity of O(log n). This means that the time it takes to access a node increases as the size of the tree increases.

Search

Searching for a node in a Binary Search Tree has a time complexity of O(log n). This means that the time it takes to search for a node increases as the size of the tree increases.

Insertion

Inserting a new node into a Binary Search Tree has an average time complexity of O(log n). This means that the time it takes to insert a new node increases as the size of the tree increases.

Deletion

Deleting a node from a Binary Search Tree has an average time complexity of O(log n). This means that the time it takes to delete a node increases as the size of the tree increases.

Space Complexity in Binary Search Trees

Space complexity refers to the amount of memory needed to store a tree. The space complexity of a Binary Search Tree is O(n), meaning that the memory needed to store a tree increases as the size of the tree increases.

C++ Code for Binary Search Trees

Now that we have an understanding of the time and space complexity of Binary Search Trees, let’s look at some code in C++ to see how they work.

Creating a Binary Search Tree

The first step in creating a Binary Search Tree is to create a node class. This class will contain the data for each node in the tree.

// Node class for Binary Search Tree
class Node { 
  public: 
    int data; 
    Node *left; 
    Node *right; 
}; 

Now that we have a node class, we can create a Binary Search Tree class. This class will contain the root node, as well as functions to insert and delete nodes.

// Binary Search Tree class 
class BST { 
  public: 
    Node *root; 
  
    // Functions to insert and delete nodes 
    void insert(int data); 
    void delete(int data); 
};

Inserting a Node

To insert a new node into a Binary Search Tree, we must first find the right place for it. We do this by starting at the root node and comparing the data of the new node to the data of the current node. If the data is lower, we move to the left child node. If the data is higher, we move to the right child node. We continue this process until we reach a node with no children, at which point we can insert the new node.

// Function to insert a new node into a Binary Search Tree
void BST::insert(int data) { 
  Node *node = new Node(); 
  node->data = data; 
  node->left = NULL; 
  node->right = NULL; 
  
  if (root == NULL) { 
    root = node; 
  } else { 
    Node *currentNode = root; 
    Node *parentNode; 
  
    while (true) { 
      parentNode = currentNode; 
  
      if (data < currentNode->data) { 
        currentNode = currentNode->left; 
 
        if (currentNode == NULL) { 
          parentNode->left = node; 
          break; 
        } 
      } 
      else { 
        currentNode = currentNode->right; 
  
        if (currentNode == NULL) { 
          parentNode->right = node; 
          break; 
        } 
      } 
    } 
  } 
} 

Deleting a Node

To delete a node from a Binary Search Tree, we must first find the node. We do this by starting at the root node and comparing the data of the node to be deleted to the data of the current node. If the data is lower, we move to the left child node. If the data is higher, we move to the right child node. We continue this process until we reach the node to be deleted.

Once we have found the node to be deleted, we have three different scenarios:

• The node has no children. In this case, we can simply delete the node.
• The node has one child. In this case, we can delete the node and replace it with its child.
• The node has two children. In this case, we must find the minimum value in the right subtree and replace the node to be deleted with this value.

// Function to delete a node from a Binary Search Tree 
void BST::delete(int data) { 
  if (root == NULL) 
    return; 
  
  Node *currentNode = root; 
  Node *parentNode = NULL; 
  
  // Find the node to be deleted 
  while (currentNode->data != data) { 
    parentNode = currentNode; 
  
    if (data < currentNode->data) { 
      currentNode = currentNode->left; 
    } 
    else { 
      currentNode = currentNode->right; 
    } 
  
    // Node to be deleted was not found 
    if (currentNode == NULL) 
      return; 
  } 
  
  // Node has no children 
  if (currentNode->left == NULL && currentNode->right == NULL) { 
    if (parentNode == NULL) { 
      root = NULL; 
    } 
    else { 
      if (parentNode->left == currentNode) 
        parentNode->left = NULL; 
      else
        parentNode->right = NULL; 
    } 
  } 
  
  // Node has one child 
  else if (currentNode->right == NULL) { 
    if (parentNode == NULL) { 
      root = currentNode->left; 
    } 
    else { 
      if (parentNode->left == currentNode) 
        parentNode->left = currentNode->left; 
      else
        parentNode->right = currentNode->left; 
    } 
  } 
  else if (currentNode->left == NULL) { 
    if (parentNode == NULL) { 
      root = currentNode->right; 
    } 
    else { 
      if (parentNode->left == currentNode) 
        parentNode->left = currentNode->right; 
      else
        parentNode->right = currentNode->right; 
    } 
  } 
  
  // Node has two children 
  else { 
    Node *successor = getSuccessor(currentNode); 
  
    if (parentNode == NULL) { 
      root = successor; 
    } 
    else { 
      if (parentNode->left == currentNode) 
        parentNode->left = successor; 
      else
        parentNode->right = successor; 
    } 
  
    successor->left = currentNode->left; 
  } 
} 

Conclusion

In conclusion, Binary Search Trees are a type of tree data structure where each node has up to two children. The structure of a Binary Search Tree makes it easy to quickly access, search, insert, and delete nodes. The time complexity for these operations is O(log n), while the space complexity is O(n).

Exercises

// Function to traverse a Binary Search Tree in-order 
void inOrder(Node* root) { 
  if (root != NULL) { 
    inOrder(root->left); 
    cout << root->data << " "; 
    inOrder(root->right); 
  } 
} 

// Function to find the minimum value in a Binary Search Tree 
int minValue(Node* root) { 
  Node* current = root; 
  
  if (current == NULL) 
    return -1; 
  
  while (current->left != NULL) 
    current = current->left; 
  
  return current->data; 
} 

// Function to find the maximum value in a Binary Search Tree 
int maxValue(Node* root) { 
  Node* current = root; 
  
  if (current == NULL) 
    return -1; 
  
  while (current->right != NULL) 
    current = current->right; 
  
  return current->data; 
} 

// Function to check if a value exists in a Binary Search Tree 
bool search(Node* root, int data) { 
  if (root == NULL) 
    return false; 
  
  if (root->data == data) 
    return true; 
  
  if (data < root->data) 
    return search(root->left, data); 
  
  else 
    return search(root->right, data); 
} 

// Function to calculate the height of a Binary Search Tree 
int height(Node* root) { 
  if (root == NULL) 
    return -1; 
  
  int leftHeight = height(root->left); 
  int rightHeight = height(root->right); 
  
  return 1 + max(leftHeight, rightHeight); 
}