Binary Search Tree Fundamentals: Concepts and Java implementation for search, insertion and deletion

Table of contents:

· What is a binary search tree?
· Implementation of binary search tree
· Search in BST
∘ Recursive
∘ Iterative
· Insert in BST
∘ Recursive
∘ Iterative
· Delete in BST

What is a binary search tree?

Binary search tree (BST) is a special type of binary tree, in which the value of each left child node is smaller the the value of the parent node, and the value of the right child node is greater than the value of the parent node.

Binary Search Tree

Basic operations of a binary search tree are:

• Search
• Traversal
• Insertion
• Deletion

In this post, I will focus on the implementation of search and insertion in BST.

Implementation of binary search tree

class Node {
  int key;
  Node left;
  Node right;
  
  Node(int x) {
    key = x;
  }
}