Binary Search Tree

A Binary Search Tree is a binary tree with a specific ordering property: for any sub-tree, the left nodes is less that the root node and the right nodes is bigger to the root node.

Searching in a Binary Search Tree is really fast thanks to its ordering property.

Insertion in a Binary Search Tree can unbalance the tree.

Find and insert operations in a unbalanced Search Tree is O(n) whereas it is O(log n) in a balanced tree.

There are 3 ways to traverse a binary tree:

• In-order: left node, root node, the then right node
• Pre-order: the root, the left node, then the right node
• Post-order: the left node, the right node, then the root node

In order in Binary Search Tree, the in-order traversal is preferred.