Binary Search Tree(BST)
What is BST Tree?
A Binary Search Tree (BST) is a data structure used to storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node.
struct Node
{
int data;
Node *left;
Node *right;
Node(int value)
{
data = value;
left = right = nullptr;
}
};
class BST
{
Node *root;
// inserting values
Node *insert(Node *node, int value)
{
if (node == nullptr)
{
return new Node(value);
}
if (value < node->data)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
// Inorder Traversal Code
void inOrder(Node *node)
{
if (node == nullptr)
{
return;
}
inOrder(node->left);
cout << node->data << sp;
inOrder(node->right);
}
// Helper function to search for a value
Node *search(Node *node, int value)
{
if (node == nullptr || node->data == value)
{
return node;
}
if (value < node->data)
{
return search(node->left, value);
}
return search(node->right, value);
}
// Finding kth Smallest Number
Node *kthSmallestUtil(Node *node, int &k)
{
if (node == nullptr)
return nullptr;
Node *left = kthSmallestUtil(node->left, k);
if (left != nullptr)
return left;
if (--k == 0)
return node;
return kthSmallestUtil(node->right, k);
}
public:
BST()
{
root = nullptr;
}
//Inserting value
void insert(int value)
{
root = insert(root, value);
}
// Print : Sorted Array(Inorder Traversal)
void inorderPrint()
{
inOrder(root);
cout << endl;
}
// Search for a value in the BST
bool search(int value)
{
Node *result = search(root, value);
return result != nullptr;
}
// Find Kth Smallest Number
int kthSmallest(int k)
{
Node *res = kthSmallestUtil(root, k);
return (res == nullptr) ? -1 : res->data;
}
};
void solve()
{
//* Sometimes you win, sometimes you learn..." - Good Wisher
BST tree;
cout << "Enter the number of elements :" << endl;
int n;
cin >> n;
cout << "Enter the elements :" << endl;
// 10 8 21 7 27 5 4 3 -1
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
tree.insert(x);
}
// Inorder Traversal : Sorted Array
cout << "Inorder Traversal :" << endl;
tree.inorderPrint();
// kth smallest element
cout << "Enter the kth smallest element to find :" << endl;
int k;
cin >> k;
// Find Kth Smallest Element
int kthSmall = tree.kthSmallest(k);
if (kthSmall == -1)
cout << "The tree has less than " << k << " elements." << endl;
else
cout << "The " << k << "th smallest element is " << kthSmall << endl;
// Search for a value
cout << "Enter value to search: ";
int value;
cin >> value;
if (tree.search(value))
{
cout << value << " is found in the BST." << endl;
}
else
{
cout << value << " is not found in the BST." << endl;
}
}Tree Traversal
In order Traversal
In order traversal visits the node in the order: Left -> Root -> Right
// Given a binary tree, print its nodes in inorder
void printInorder(struct Node* node)
{
if (node == NULL)
return;
// First recur on left child
printInorder(node->left);
// Then print the data of node
cout << node->data << " ";
// Now recur on right child
printInorder(node->right);
}Pre Order Traversal
Preorder traversal visits the node in the order: Root -> Left -> Right
// Given a binary tree, print its nodes in preorder
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
// First print data of node
cout << node->data << " ";
printPreorder(node->left);
printPreorder(node->right);
}
Post Order Traversal
Post order traversal visits the node in the order: Left -> Right -> Root
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
// Now deal with the node
cout << node->data << " ";
}What is Perfectly Balanced Binary Tree?
A balanced binary tree will follow the following conditions:
The absolute difference of heights of left and right subtrees at any node is less than 1.
For each node, its left subtree is a balanced binary tree.
For each node, its right subtree is a balanced binary tree.
When BST Best and Worst Complexity?
Best Case Scenario
The best-case scenario for a BST occurs when the tree is perfectly balanced. In a balanced BST, each level of the tree is fully populated, leading to optimal performance.
Search, Insertion, Deletion:
Time Complexity: O(logn)
Space Complexity: O(n)
Reason: In a balanced BST, the height of the tree is log(n). Operations like search, insertion, and deletion involve traversing from the root to a leaf, which takes logn steps in the best case.
Worst Case Scenario
The worst-case scenario for a BST occurs when the tree is completely unbalanced, resembling a linked list. This can happen if elements are inserted in sorted order.
Search, Insertion, Deletion:
Time Complexity: O(n)
Space Complexity: O(n)
Reason: In an unbalanced BST, the height of the tree can be N. Operations like search, insertion, and deletion involve traversing from the root to a leaf, which takes N steps in the worst case.
Binary Search Tree Related Leet Code Questions
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root)
return new TreeNode(val);
if (root->val > val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
};You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val) {
return root;
}
if (val < root->val) {
return searchBST(root->left, val);
}
return searchBST(root->right, val);
}
};Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
class Solution {
public:
vector<int> numbers;//declare it globally, it contains the inorder traversal of BST
void inorderpush(TreeNode* root){
if(root==nullptr){
return;
}
inorderpush(root->left);
numbers.push_back(root->val);//inserts the element in array
inorderpush(root->right);
}
bool isValidBST(TreeNode* root) {
inorderpush(root);
for(int i=0;i<numbers.size()-1;i++){
if(numbers[i+1]<=numbers[i]){
return false;//if array is not strictly increasing
}
}
return true; //if array is strictly increasing
}
};Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
class Solution {
public:
int ans;
int rangeSumBST(TreeNode* root, int low, int high) {
if(root == 0){
return ans;
}
int value = root->val;
if(value >= low && value <= high){
ans += value;
}
rangeSumBST(root->left,low,high);
rangeSumBST(root->right,low,high);
return ans;
}
};897. Increasing Order Search Tree :
Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
class Solution {
public:
void inorder(TreeNode*& ans, TreeNode* root) {
if (!root)
return;
inorder(ans, root->left);
ans->right = new TreeNode(root->val);
ans = ans->right;
inorder(ans, root->right);
}
TreeNode* increasingBST(TreeNode* root) {
TreeNode* temp;
TreeNode* ans = new TreeNode();
temp = ans;
inorder(ans, root);
return temp->right;
}
};Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
class Solution {
public:
int count = 0;
int ans = 0;
void inOrderTraversal(TreeNode* root, int k) {
if (root == nullptr)
return;
inOrderTraversal(root->left, k);
count++;
if (count == k) {
ans = root->val;
return;
}
inOrderTraversal(root->right, k);
}
int kthSmallest(TreeNode* root, int k) {
inOrderTraversal(root, k);
return ans;
}
};Last updated