Binary Search Tree

A Binary Search Tree (BST) is a type of binary tree data structure in which each node contains a unique key and satisfies a specific ordering property

BST Information

• All nodes in the left subtree of a node contain values strictly less than the node’s value.
• All nodes in the right subtree of a node contain values strictly greater than the node’s value.
• BSTs are widely used in database indexing, symbol tables, range queries, and are foundational for advanced structures like AVL tree and Red-Black tree. In problem solving, BSTs are used in problems where we need to maintain sorted stream of data.
• Operations like search, insertion, and deletion work in O(Log n) time for a balanced binary search tree. In the worst-case (unbalanced), these degrade to O(n). With self-balancing BSTs like AVL and Red Black Trees, we can ensure the worst case as O(Log n).

Correct and Incorrect Binary Search Trees

More Information Visit W3Schools.com