Binary Search Trees
Binary search trees (BSTs) are a type of binary tree where the left child of a node is smaller than the node, and the right child is greater. This organization allows for efficient search, insert, and delete operations.
A binary search tree is commonly represented by a root node, which is the topmost node in the tree. Each node in the tree has a value and two child nodes, referred to as the left child and the right child.
Here's an example of creating and searching for an element in a binary search tree in Java:
SNIPPET
1class Main {
2 public static void main(String[] args) {
3
4 // Creating a binary search tree
5 TreeNode rootNode = new TreeNode(8);
6 rootNode.left = new TreeNode(3);
7 rootNode.right = new TreeNode(10);
8 rootNode.left.left = new TreeNode(1);
9 rootNode.left.right = new TreeNode(6);
10 rootNode.left.right.left = new TreeNode(4);
11 rootNode.left.right.right = new TreeNode(7);
12 rootNode.right.right = new TreeNode(14);
13 rootNode.right.right.left = new TreeNode(13);
14
15 // Searching in the binary search tree
16 TreeNode result = search(rootNode, 6);
17
18 // Printing the result
19 if (result != null) {
20 System.out.println("Element found: " + result.val);
21 } else {
22 System.out.println("Element not found.");
23 }
24 }
25
26 public static TreeNode search(TreeNode rootNode, int value) {
27 if (rootNode == null || rootNode.val == value) {
28 return rootNode;
29 }
30
31 if (value < rootNode.val) {
32 return search(rootNode.left, value);
33 }
34
35 return search(rootNode.right, value);
36 }
37}
38
39class TreeNode {
40 int val;
41 TreeNode left;
42 TreeNode right;
43
44 public TreeNode(int val) {
45 this.val = val;
46 }
47}xxxxxxxxxx47
}class Main { public static void main(String[] args) { // Creating a binary search tree TreeNode rootNode = new TreeNode(8); rootNode.left = new TreeNode(3); rootNode.right = new TreeNode(10); rootNode.left.left = new TreeNode(1); rootNode.left.right = new TreeNode(6); rootNode.left.right.left = new TreeNode(4); rootNode.left.right.right = new TreeNode(7); rootNode.right.right = new TreeNode(14); rootNode.right.right.left = new TreeNode(13); // Searching in the binary search tree TreeNode result = search(rootNode, 6); // Printing the result if (result != null) { System.out.println("Element found: " + result.val); } else { System.out.println("Element not found."); } } public static TreeNode search(TreeNode rootNode, int value) { if (rootNode == null || rootNode.val == value) { return rootNode; }OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment