A Binary Search Tree is a Binary tree in which all the nodes have following properties.
- Left subtree of a node contains all the nodes having values lesser than the node.
- Right subtree of a node contains all the nodes having values higher than the node.
- Both the left and right subtree is also a Binary Search Tree.
As the name suggests, this data structure is mainly used for faster searching. In order to do that, restrictions are applied while inserting/deleting an element into the tree. As a result of these restrictions, worst case search time complexity remains at O(log n).
Below are some examples of Binary Search Trees.
Let’s have a look into some of the most popular and useful topics in Binary Search Tree data structures.
- Binary Search Tree explanation
- Inserting a node in Binary Search Tree
- Deleting a node in Binary Search Tree
- Searching a node in Binary Search Tree
- Find minimum value node in Binary Search Tree
- Find maximum value node in Binary Search Tree
- Find Kth smallest node in Binary Search Tree
- Find Kth largest node in Binary Search Tree
- Least common ancestor of given node in Binary Search Tree
- Check whether a binary tree is Binary search tree
- AVL tree explanation
- Check whether a Binary Search Tree is AVL Tree
- AVL Tree self-balancing rotations – Right rotation
- AVL Tree self-balancing rotations – Left Rotation
- AVL Tree self-balancing rotations – Left Right Rotation
- AVL Tree self-balancing rotations – Right Left Rotation
- Inserting a node in AVL Tree
- Deleting a node in AVL Tree