Binary Search Trees
Binary search trees (BSTs) are a special type of binary tree that satisfies an additional constraint: the nodes in the left subtree must have key values less than the key value of the parent, and the nodes in the right subtree must have key values greater than the key value of the parent.
In other words, in a BST, the left child of any node has a smaller value, and the right child has a larger value. This property of BSTs enables efficient searching, insertion, and deletion operations.
BSTs are commonly used in various applications, such as implementing symbol tables, dictionaries, and binary search algorithms.
Here's an example of a binary search tree:
1 50
2 / \
3 30 70
4 / \ / \
520 40 60 80To implement a BST, we need to define a class that represents a node in the tree and another class that represents the binary search tree itself.
Let's create a BST class with the following functionalities:
void insert(int data): Inserts a new node with the given data into the BSTvoid print(): Prints the contents of the BST in sorted order
Here's an implementation of the BST class in Java:
1class Node {
2 int data;
3 Node left;
4 Node right;
5
6 Node(int data) {
7 this.data = data;
8 this.left = null;
9 this.right = null;
10 }
11}
12
13class BST {
14 Node root;
15
16 BST() {
17 this.root = null;
18 }
19
20 void insert(int data) {
21 this.root = insertRec(this.root, data);
22 }
23
24 Node insertRec(Node root, int data) {
25 if (root == null) {
26 root = new Node(data);
27 return root;
28 }
29
30 if (data < root.data) {
31 root.left = insertRec(root.left, data);
32 } else if (data > root.data) {
33 root.right = insertRec(root.right, data);
34 }
35
36 return root;
37 }
38
39 void print() {
40 printRec(this.root);
41 }
42
43 void printRec(Node root) {
44 if (root != null) {
45 printRec(root.left);
46 System.out.print(root.data + " ");
47 printRec(root.right);
48 }
49 }
50}xxxxxxxxxx}class Main { public static void main(String[] args) { // Binary Search Tree BST bst = new BST(); bst.insert(50); bst.insert(30); bst.insert(20); bst.insert(40); bst.insert(70); bst.insert(60); bst.insert(80); // Print the tree bst.print(); } static class Node { int data; Node left; Node right; Node(int data) { this.data = data; this.left = null; this.right = null; } } static class BST {