Data Structure Questions and Answers – Binary Search Tree

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Binary Search Tree”.

1. Construct a binary search tree with the below information.
The preorder traversal of a binary search tree 10, 4, 3, 5, 11, 12.

A)

data-structure-questions-answers-binary-search-tree-q11a

B)

data-structure-questions-answers-binary-search-tree-q11b

C)

data-structure-questions-answers-binary-search-tree-q11c

D)

data-structure-questions-answers-binary-search-tree-q11d

Explanation: Preorder Traversal is 10, 4, 3, 5, 11, 12. Inorder Traversal of Binary search tree is equal to ascending order of the nodes of the Tree. Inorder Traversal is 3, 4, 5, 10, 11, 12. The tree constructed using Preorder and Inorder traversal is

data-structure-questions-answers-binary-search-tree-q11c

2. Which of the following is false about a binary search tree?
A) The left child is always lesser than its parent
B) The right child is always greater than its parent
C) The left and right sub-trees should also be binary search trees
D) In order sequence gives decreasing order of elements

Explanation: Binary search trees will always give ascending order of elements in their order series. Regarding binary search trees, everything else is valid.

3. How to search for a key in a binary search tree?
A)

public Tree search(Tree root, int key)
{
	if( root == null || root.key == key )
        {
		return root;
	}
	if( root.key < key )
        {
		return search(root.right,key);
	}
	else
	return search(root.left,key);
}

B)

public Tree search(Tree root, int key)
{
	if( root == null || root.key == key )
        {
		return root;
	}
	if( root.key < key )
        {
		return search(root.left,key);
	}
	else
	return search(root.right,key);
}

C)

public Tree search(Tree root, int key)
{
	if( root == null)
        {
		return root;
	}
	if( root.key < key )
        {
		return search(root.right,key);
	}
	else
		return search(root.left,key);
}

D)

public Tree search(Tree root, int key)
{
	if( root == null)
        {
		return root;
	}
	if( root.key < key )
        {
		return search(root.right.right,key);
	}
	else
		return search(root.left.left,key);
}


Explanation: Since the left child is smaller than the parent, if the root’s key is greater than the given key, we only look at the left sub-tree, and vice versa.

4. What is the speciality about the inorder traversal of a binary search tree?
A) It traverses in a non increasing order
B) It traverses in an increasing order
C) It traverses in a random fashion
D) It traverses based on priority of the node

Explanation: An inorder traversal can return the elements in increasing order since a binary search tree has elements that are less than the node to the left and those that are greater than the node to the right.

5. What does the following piece of code do?

public void func(Tree root)
{
	func(root.left());
	func(root.right());
	System.out.println(root.data());
}

A) Preorder traversal
B) Inorder traversal
C) Postorder traversal
D) Level order traversal

Explanation: The left child is visited first, then the right child, and finally the parent in a postorder traversal.

6. What does the following piece of code do?

public void func(Tree root)
{
	System.out.println(root.data());
	func(root.left());
	func(root.right());
}

A) Preorder traversal
B) Inorder traversal
C) Postorder traversal
D) Level order traversal

Explanation: The parent is visited first, followed by the left child, and finally the right child in a preorder traversal.

7. How will you find the minimum element in a binary search tree?
A)

public void min(Tree root)
{
	while(root.left() != null)
	{
		root = root.left();
	}
	System.out.println(root.data());
}

B)

public void min(Tree root)
{
	while(root != null)
	{
		root = root.left();
	}
	System.out.println(root.data());
}

C)

public void min(Tree root)
{
	while(root.right() != null)
	{
		root = root.right();
	}
	System.out.println(root.data());
}

D)

public void min(Tree root)
{
	while(root != null)
	{
		root = root.right();
	}
	System.out.println(root.data());
}


Explanation: In a binary search tree, iterating to the leftmost leaf of the root would give the minimum element since all the elements less than a given node will be to the left.

8. How will you find the maximum element in a binary search tree?
A)

public void max(Tree root)
{
	while(root.left() != null)
	{
		root = root.left();
	}
	System.out.println(root.data());
}

B)

public void max(Tree root)
{
	while(root != null)
	{
		root = root.left();
	}
	System.out.println(root.data());
}

C)

public void max(Tree root)
{
	while(root.right() != null)
	{
		root = root.right();
	}
	System.out.println(root.data());
}

D)

public void max(Tree root)
{
	while(root != null)
	{
		root = root.right();
	}
	System.out.println(root.data());
}


Explanation: In a binary search tree, iterating through the tree to the rightmost leaf of the root would give the maximum element since all the elements greater than a given node are towards the right.

9. What are the worst case and average case complexities of a binary search tree?
A) O(n), O(n)
B) O(logn), O(logn)
C) O(logn), O(n)
D) O(n), O(logn)

Explanation: The worst case scenario occurs when the tree is skewed (to the left or right), in which case you must process all of the tree’s nodes, resulting in O(n) complexity, rather than O(logn) since you only process half of the tree.

10. Given that 2 elements are present in the tree, write a function to find the LCA(Least Common Ancestor) of the 2 elements.
A)

public void lca(Tree root,int n1, int n2)
{
	while (root != NULL)
        {
            if (root.data() > n1 && root.data() > n2)
            root = root.right();
            else if (root.data() < n1 && root.data() < n2)
            root = root.left();
	    else break;
        }
        System.out.println(root.data());
}

B)

public void lca(Tree root,int n1, int n2)
{
    while (root != NULL)
    {
        if (root.data() > n1 && root.data() < n2)
        root = root.left();
        else if (root.data() < n1 && root.data() > n2)
        root = root.right();
	else break;
    }
    System.out.println(root.data());
}

C)

public void lca(Tree root,int n1, int n2)
{
    while (root != NULL)
    {
        if (root.data() > n1 && root.data() > n2)
        root = root.left();
        else if (root.data() < n1 && root.data() < n2)
        root = root.right();
	else break;
    }
    System.out.println(root.data());
}

D)

public void lca(Tree root,int n1, int n2)
{
    while (root != NULL)
    {
        if (root.data() > n1 && root.data() > n2)
        root = root.left.left();
        else if (root.data() < n1 && root.data() < n2)
        root = root.right.right();
	else break;
    }
    System.out.println(root.data());
}


Explanation: The lesser elements are to the left and greater elements are to the right in a binary search tree; we use this property here and iterate through the tree until we reach a point where the two elements are on opposite sides of the node; this is the least common ancestor of the two given elements.

11. What are the conditions for an optimal binary search tree and what is its advantage?
A) The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost
B) You should know the frequency of access of the keys, improves the lookup time
C) The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time
D) The tree should be just modified and improves the lookup time

Explanation: For the best binary scan, The tree can not be changed, and we need to figure out how often keys are used. The lookup cost is reduced with optimal binary search.

A rooted binary tree whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in the node’s right subtree is known as a binary search tree (BST). A binary tree is a type of data structure for storing data in an ordered manner, such as numbers. Binary search trees are used to implement dynamic sets which lookup tables and allow for quick lookup, addition, and removal of data objects. Since each comparison skips about half of the remaining tree in a BST, the entire lookup takes time proportional to the binary logarithm of the number of items contained in the tree.

Leave a Reply

Your email address will not be published. Required fields are marked *