**Binary Tree-**

Before you go through this article, make sure that you gone through the previous article on **Binary Trees**.

We have discussed-

- Binary tree is a special tree data structure.
- In a binary tree, each node can have at most 2 children.
- In a binary tree, nodes may be arranged in any random order.

In this article, we will discuss about Binary Search Trees.

**Binary Search Tree-**

Binary Search Tree is a special kind of binary tree in which nodes are arranged in a specific order. |

In a binary search tree (BST), each node contains-

- Only smaller values in its left sub tree
- Only larger values in its right sub tree

**Example-**

**Number of Binary Search Trees-**

**Example-**

Number of distinct binary search trees possible with 3 distinct keys

= ^{2×3}C_{3} / 3+1

= ^{6}C_{3} / 4

= 5

If three distinct keys are A, B and C, then 5 distinct binary search trees are-

**Binary Search Tree Construction-**

Let us understand the construction of a binary search tree using the following example-

**Example-**

Construct a Binary Search Tree (BST) for the following sequence of numbers-

50, 70, 60, 20, 90, 10, 40, 100

When elements are given in a sequence,

- Always consider the first element as the root node.
- Consider the given elements and insert them in the BST one by one.

The binary search tree will be constructed as explained below-

**Insert 50-**

**Insert 70-**

- As 70 > 50, so insert 70 to the right of 50.

**Insert 60-**

- As 60 > 50, so insert 60 to the right of 50.
- As 60 < 70, so insert 60 to the left of 70.

**Insert 20-**

- As 20 < 50, so insert 20 to the left of 50.

**Insert 90-**

- As 90 > 50, so insert 90 to the right of 50.
- As 90 > 70, so insert 90 to the right of 70.

**Insert 10-**

- As 10 < 50, so insert 10 to the left of 50.
- As 10 < 20, so insert 10 to the left of 20.

**Insert 40-**

- As 40 < 50, so insert 40 to the left of 50.
- As 40 > 20, so insert 40 to the right of 20.

**Insert 100-**

- As 100 > 50, so insert 100 to the right of 50.
- As 100 > 70, so insert 100 to the right of 70.
- As 100 > 90, so insert 100 to the right of 90.

This is the required Binary Search Tree.

To gain better understanding about Binary Search Trees,

**PRACTICE PROBLEMS BASED ON BINARY SEARCH TREES-**

**Problem-01:**

A binary search tree is generated by inserting in order of the following integers-

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is _____.

- (4, 7)
- (7, 4)
- (8, 3)
- (3, 8)

**Solution-**

Using the above discussed steps, we will construct the binary search tree.

The resultant binary search tree will be-

Clearly,

- Number of nodes in the left subtree of the root = 7
- Number of nodes in the right subtree of the root = 4

Thus, Option (B) is correct.

**Problem-02:**

How many distinct binary search trees can be constructed out of 4 distinct keys?

- 5
- 14
- 24
- 35

**Solution-**

Number of distinct binary search trees possible with 4 distinct keys

= ^{2n}C_{n} / n+1

= ^{2×4}C_{4} / 4+1

= ^{8}C_{4} / 5

= 14

Thus, Option (B) is correct.

**Problem-03:**

The numbers 1, 2, …, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be-

- p
- p+1
- n-p
- n-p+1

**Solution-**

Let n = 4 and p = 3.

Then, given options reduce to-

- 3
- 4
- 1
- 2

Our binary search tree will be as shown-

Clearly, first inserted number = 1.

Thus, Option (C) is correct.

**Problem-04:**

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with given set so that it becomes a binary search tree?

- 0
- 1
- n!
- C(2n, n) / n+1

**Solution-**

Option (B) is correct.

To watch video solutions and practice more problems,

**Download Handwritten Notes Here-**

**Next Article-** **Binary Search Tree Traversal**

Get more notes and other study material of **Data Structures**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.