Binary Search Tree (BST)

A Binary Search Tree (BST) is a type of binary tree that satisfies the following properties:

1. For any node in the tree, all values in its left subtree are less than its value.
2. For any node in the tree, all values in its right subtree are greater than its value.
3. The left and right subtrees of each node are also Binary Search Trees.

These properties make BSTs an efficient data structure for searching, insertion, and deletion operations.

Diagram:

          6
        /   \
       4     8
      / \   / \
     3   5 7   9

• The diagram represents a Binary Search Tree with values 3, 4, 5, 6, 7, 8, and 9.
• The root of the tree is 6, and each node has a left and right child.
• The left subtree of each node contains values less than the node’s value, and the right subtree contains values greater than the node’s value.

Code in Java:

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

class BinarySearchTree {
    Node root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int value) {
        root = insertNode(root, value);
    }

    private Node insertNode(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertNode(root.left, value);
        } else if (value > root.value) {
            root.right = insertNode(root.right, value);
        }

        return root;
    }

    public boolean search(int value) {
        return searchNode(root, value);
    }

    private boolean searchNode(Node root, int value) {
        if (root == null) {
            return false;
        }

        if (value == root.value) {
            return true;
        } else if (value < root.value) {
            return searchNode(root.left, value);
        } else {
            return searchNode(root.right, value);
        }
    }

    public void inorderTraversal() {
        inorder(root);
    }

    private void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.value + " ");
            inorder(root.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        bst.insert(6);
        bst.insert(4);
        bst.insert(8);
        bst.insert(3);
        bst.insert(5);
        bst.insert(7);
        bst.insert(9);

        System.out.println("Inorder Traversal:");
        bst.inorderTraversal();

        int searchValue = 5;
        if (bst.search(searchValue)) {
            System.out.println("\n" + searchValue + " is found in the BST.");
        } else {
            System.out.println("\n" + searchValue + " is not found in the BST.");
        }
    }
}

Explanation:

• The code defines two classes: Node and BinarySearchTree.
• The Node class represents a node in the BST with its value, left child, and right child.
• The BinarySearchTree class represents the BST and provides methods for the insertion, search, and inorder traversal.
• The insert method inserts a new node into the BST based on its value.It recursively traverses the tree to find the appropriate position for insertion.
• The search method searches for a given value in the BST. It recursively traverses the tree, comparing the value with each node’s value until a match is found or the end of the tree is reached.
• The inorderTraversal method performs an inorder traversal of the BST, which visits the nodes in ascending order. It recursively traverses the left subtree, visits the current node, and then recursively traverses the right subtree.
• In the main method, a new BST is created, and nodes with values 6, 4, 8, 3, 5, 7, and 9 are inserted. The inorder traversal is performed, and the search method is used to search for the value 5.

Output:

Inorder Traversal:
3 4 5 6 7 8 9
5 is found in the BST

Time & Space complexity of operations in a BST:

Operation	Time Complexity	Space Complexity
Insertion	O(log n)	O(log n)
Search	O(log n)	O(log n)
Deletion	O(log n)	O(log n)
Inorder Traversal	O(n)	O(log n)
Preorder Traversal	O(n)	O(log n)
Postorder Traversal	O(n)	O(log n)
Height/Depth	O(n)	O(log n)

Important formulas to calculate various properties in a Binary Search Tree:

1. Height of BST:
   • Formula: height = log2(n + 1) - 1
   • n represents the number of nodes in the BST.
2. Number of Nodes in BST:
   • Formula: n = 2^(height+1) - 1
   • height refers to the height of the BST.
3. Number of Leaf Nodes in BST:
   • Formula: leafNodes = (n + 1) / 2
   • n represents the number of nodes in the BST.
4. Number of Internal Nodes in BST:
   • Formula: internalNodes = n - leafNodes
   • n refers to the number of nodes in the BST.
   • leafNodes represents the number of leaf nodes in the BST.
5. Level of a Node in BST:
   • The level of a node is the number of edges in the path from the root node to that node.
   • It can be calculated by traversing the BST from the root node to the target node and counting the number of edges.

Advantages of Binary Search Tree:

1. Efficient Search: BST provides an efficient way to search for a specific key. On average, the search operation takes O(log n) time complexity, where n is the number of nodes in the tree.
2. Efficient Insertion and Deletion: BST allows for efficient insertion and deletion operations. On average, these operations also take O(log n) time complexity.
3. Sorted Order: The keys in a BST are stored in sorted order, which makes it easy to retrieve keys in ascending or descending order.

Note: also read about Types of Views & Binary Trees

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py