Lecture 295:- BST intro

BST stands for Binary Search Tree. It is a special type of binary tree in which the nodes are arranged in a particular order, allowing for efficient searching, insertion, and deletion operations.

The key properties of a Binary Search Tree are as follows:

1. Binary Tree Structure: A BST is a binary tree, meaning each node has at most two children, commonly referred to as the left child and the right child.
2. Ordering Property: The nodes in a BST are arranged in a specific order, such that for each node:
   • All nodes in the left subtree have keys (values) less than the node's key.
   • All nodes in the right subtree have keys greater than the node's key.
   • There are no duplicate keys (no two nodes have the same key).
3. Searching: Due to the ordering property, searching for a specific key in a BST can be done efficiently in O(log n) time on average, where "n" is the number of nodes in the tree. This makes BSTs suitable for fast searching.
4. Insertion and Deletion: Inserting a new node and deleting an existing node in a BST while maintaining the ordering property can also be done in O(log n) time on average.
5. In-order Traversal: When the nodes of a BST are visited in an in-order traversal (left-root-right), they are visited in ascending order of their keys, which is a useful property for various operations.

BSTs are widely used in computer science and programming due to their efficiency in searching, insertion, and deletion operations. They are used to implement many data structures, such as sets, dictionaries, and associative arrays.

However, it's important to note that the efficiency of a BST depends on its balanced nature. In the worst-case scenario, when the tree is highly unbalanced (resembling a linear linked list), the time complexity for search, insert, and delete operations can degrade to O(n), making it less efficient. To overcome this, various balanced BST variants, such as AVL trees, Red-Black trees, and Splay trees, have been developed to maintain the balance of the tree and ensure efficient operations in all cases.