A binary search tree (BST) is a data structure that is commonly used in computer science to store and retrieve data efficiently. It is called a "binary" search tree because each node has at most two children, and it is called a "search" tree because it allows for efficient search and retrieval of data.
All elements on left are less than the root and all elements on right are greater than the root!
Time Complexity:
Access -> O(n).
Deletion -> O(n).
Searching -> O(n)
Insertion -> O(n)
Inorder traversal is sorted!
https://leetcode.com/problems/search-in-a-binary-search-tree/
public class BinarySearchTree {
// Node class represents a node in the binary tree
static class Node {
int value;
Node left;
Node right;
// Constructor to create a new node
Node(int value) {
this.value = value;
left = null;
right = null;
}
}
// Root of the binary tree
Node root;
// Constructor to create a binary search tree
BinarySearchTree() {
root = null;
}
// Method to search a value in the binary tree
boolean search(int value) {
return search(root, value);
}
// Helper method to search a value in the binary tree
boolean search(Node node, int value) {
// If the tree is empty, return false
if (node == null) {
return false;
}
// If the value is found at the root, return true
if (node.value == value) {
return true;
}
// Recursively search in the left or right subtree
if (value < node.value) {
return search(node.left, value);
} else {
return search(node.right, value);
}
}
}
Kth largest node
So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.
Thank you, Have a nice day !!