What is BST (Binary Search Tree)?

Question is usually something like explain BST or Binary Search Tree.

Answer:

A binary search tree (BST) is a tree in which every node's left sub-tree has a key less than the node's key, and every right sub-tree has a key greater than the node's key.  The major advantage of binary search trees is that the related sorting algorithms and search algorithms, such as in-order traversal, can be very efficient. This data structure is perfect for advanced interview questions.

During the interview you can expect a wide range of questions, such as searching a binary tree for a specific value, inserting and deleting nodes in the tree or sorting the tree.  If you are asked to calculate the execution time of the algorithm you are implementing, always keep in mind the worst-case scenario, which is when the unbalanced tree resembles a linked list.

The image to shows a sample Binary search tree with root 6 and leaves 1, 5 and 7.