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