Q8,paper 2,June 12. A binary search tree is a binary tree

Options (A) All items in the left subtree are less than root            (B) All items in the right subtree are greater than or equal to the root                                  (C) Each sub tree is itself a binary search tree    (d) all the above.

Answer (D).All the above.

Explanation. Binary search trees keep their keys in sorted order, so that look up and other operations can use the principle of binary search,when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip over half of the tree, so that each lookup/insertion/deletion takes the log of the number of items stored in the tree. This is much better than the linear time required to find items by key in an unsorted array, but slower than the corresponding operations on hash tables.

The common properties of binary search trees are as follows:

• One node is designated the Root of the tree.
• Each internal node contains a key and has two subtrees.
• The leaves (final nodes) of the tree contain no key. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.
• Each subtree is itself a binary search tree.
• The left subtree of a node contains only nodes with keys strictly less than the node's key.
• The right subtree of a node contains only nodes with keys strictly greater than the node's key.

·         The shape of the binary search tree totally depends on the order of insertions, and it can be degenerated. This is one of the disadvantage also.