The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16, 4, 2. What is the height of the binary search tree?(Here height is defined as number of edges on longest path from root to a leaf)a)2b)3c)4d)5Correct answer is option 'C'. Can you explain this answer?

Question

Answer

Binary Search Tree:

A binary search tree is a binary tree, i.e., a tree in which each node has at most two children, such that the value in each node is greater than or equal to any value stored in its left sub-tree and less than or equal to any value stored in its right sub-tree.

In simple terms, the left subtree of a node contains only nodes with keys lesser than the node’s key and the right subtree of a node contains only nodes with keys greater than the node’s key.

Insertion of Nodes:

We start with an empty binary search tree.

First, we insert 10 as the root node.

Then, we insert 1 to the left of 10 as it is less than 10.

Next, we insert 3 to the right of 1 as it is greater than 1.

Then, we insert 5 to the right of 3 as it is greater than 3.

Next, we insert 15 to the right of 10 as it is greater than 10.

Then, we insert 12 to the left of 15 as it is less than 15.

Next, we insert 16 to the right of 15 as it is greater than 15.

Then, we insert 4 to the right of 3 as it is greater than 3 but less than 5.

Finally, we insert 2 to the left of 3 as it is less than 3.

Height of Binary Search Tree:

The height of a binary search tree is defined as the number of edges on the longest path from the root node to a leaf node.

The longest path in this binary search tree is from the root node 10 to the leaf node 2.

The path is as follows: 10 → 1 → 3 → 5 → 4 → 2.

The number of edges in this path is 5.

Therefore, the height of the binary search tree is 5.

Therefore, the correct answer is option C, i.e., height of the binary search tree is 4.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company