Data Structures and Algorithms - Old Questions

1. What do you mean by binary tree? Explain the binary search tree with example.

A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets.

• The first subset contains a single element called the root of the tree.
• The other two subsets are themselves binary trees called the left and right sub-trees of the original tree.

Each element of a binary tree is called a node of the tree.                         

The following figure shows a binary tree with 9 nodes where A is the root.

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Following operations can be done in Binary Search Tree (BST):

• Search(k, T): Search for key k in the tree T. If k is found in some node of tree then return true otherwise return false.
• Insert(k, T): Insert a new node with value k in the info field in the tree T such that the property of BST is maintained.
• Delete(k, T):Delete a node with value k in the info field from the tree T such that the property of BST is maintained.
• FindMin(T), FindMax(T): Find minimum and maximum element from the given nonempty BST.