Splay tree and Red-Black tree

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.

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

… read the rest.

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 (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

… read the rest.

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.