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:

1. The absolute difference of heights of left and right subtrees at any node is less than 1.

2. For each node, its left subtree is a balanced binary tree.

3. 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(log⁡n)

  • 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 log⁡n 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

Binary Search Tree - LeetCodeLeetCode

701. Insert into a Binary Search Tree:

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;
    }
};

700. Search in a Binary Search Tree

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);
    }
};

98. Validate Binary Search Tree

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   
    }
};

938. Range Sum of BST

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;
    }
};

230. Kth Smallest Element in a BST

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;
    }
};