Binary Search Trees
A binary search tree (BST) is a type of binary tree where each node has a key and its key is greater than all the keys present in its left subtree and less than all the keys present in its right subtree.
Binary search trees are highly efficient data structures that enable fast searching, insertion, and deletion of elements, making them suitable for a wide range of applications.
Main Properties of Binary Search Trees
Value Ordering: In a BST, the values are ordered in a specific way. The left subtree of a node contains values less than the node's value, and the right subtree contains values greater than the node's value.
Unique Keys: BSTs typically do not allow duplicate keys. If a key already exists in the tree and an attempt is made to insert it again, the duplicate key will be ignored.
Efficient Search: Due to their ordered nature, BSTs provide efficient search operations. The search operation compares the target key with the keys of the nodes and navigates to the left or right subtree accordingly, eliminating a significant portion of the search space in each comparison.
Java Implementation of Binary Search Tree
Here's a Java implementation of a binary search tree, including operations for insertion and inorder traversal:
1public class BinarySearchTree {
2
3 static class Node {
4 int key;
5 Node left;
6 Node right;
7
8 public Node(int key) {
9 this.key = key;
10 this.left = null;
11 this.right = null;
12 }
13 }
14
15 static Node insert(Node root, int key) {
16 if (root == null) {
17 return new Node(key);
18 }
19
20 if (key < root.key) {
21 root.left = insert(root.left, key);
22 } else if (key > root.key) {
23 root.right = insert(root.right, key);
24 }
25
26 return root;
27 }
28
29 static void inorderTraversal(Node root) {
30 if (root != null) {
31 inorderTraversal(root.left);
32 System.out.print(root.key + " ");
33 inorderTraversal(root.right);
34 }
35 }
36
37 public static void main(String[] args) {
38 Node root = null;
39 root = insert(root, 50);
40 insert(root, 30);
41 insert(root, 20);
42 insert(root, 40);
43 insert(root, 70);
44 insert(root, 60);
45 insert(root, 80);
46
47 System.out.println("Inorder traversal of the binary search tree:");
48 inorderTraversal(root);
49 }
50} xxxxxxxxxx}public class BinarySearchTree { static class Node { int key; Node left; Node right; public Node(int key) { this.key = key; this.left = null; this.right = null; } } static Node insert(Node root, int key) { if (root == null) { return new Node(key); } if (key < root.key) { root.left = insert(root.left, key); } else if (key > root.key) { root.right = insert(root.right, key); } return root; } static void inorderTraversal(Node root) {