Performance of Binary Search Tree (BST) is proportional to its height O(h). To achieve best performance, it is important to balance the tree. AVL tree, Red-Black tree and Splash tree are popular self-balacing BSTs. Like AVL tree, Splay tree and … read the rest. “Splay tree and Red-Black tree”

# BST

# AVL tree

Binary Search Tree (BST) becomes ineffective, O(n) worst case if not balanced. Any practical usage of BST requires a balanced tree. AVL tree is a self-balancing binary search tree which guarantees O(log n) performance.

- AVL tree balances itself on insertion

# Binary Search Tree Operations (Search, Insertion, Deletion, Successor, Predecessor, Minimum)

### Search

Searching for a key in Binary Search Tree (BST). Time complexity O(h) where h being the height of the tree. To leverage the best of BST search, the BST has to be height balanced.

/** * Search in binary… read the rest. “Binary Search Tree Operations (Search, Insertion, Deletion, Successor, Predecessor, Minimum)”

# Binary Search Tree (BST)

- BST (Binary Search Tree) is a binary tree in which
- Left node and its children are smaller than the root.
- Right node and its children are greater than the root.
- No duplicate nodes.

- InOrder traversal of BST produces sorted output

# Test if the given tree is binary search tree (BST)

### Problem

Test if the given binary tree is a binary search tree. Remember binary tree has utmost 2 children per node. Binary search tree follows a simple rule that left child is smaller than the root and right child is … read the rest. “Test if the given tree is binary search tree (BST)”