Question

Draw the BST where the data value at each node is an integer and the values are entered in the following order 36,22,10,44,42,16,25,3,23,24 solution

Answer 1

Answer and Explanation:

A BST is the short form for Binary Search Tree. It is a special type of binary tree data structure in which nodes are arranged in a particular order such that;

i. the left subtree of a particular node should always contain nodes whose key values are less than that of the key value of the node itself.

ii. the right subtree of a particular node should always contain nodes whose key values are greater than that of the key value of the node itself.

iii. the right and left subtrees should also be a binary search tree.

For the given set of data:

36,22,10,44,42,16,25,3,23,24;

The equivalent binary search tree is attached to this response.

As shown in the attachment:

i. the first data value (36) is the root node value.

ii. the second value (22) is less than the root node value (36), therefore, 22 goes to the left of the root node.

iii. the third value is 10. This is less than 36 and then also less than 22, so 10 goes to the left of 22.

iv. the fourth value is 44. This is greater than the root node value (36), therefore, 44 goes to the right of the root node.

v. the fifth value is 42. This is greater than the root value (36) so it is going to be positioned somewhere at the right of the root node. But it is less than the value (44) of the direct right node of the root node. Therefore, 42 goes to the left of the direct right (44) of the root node.

vi. the sixth value is 16. This is less than the root node value (36). So it is going to be positioned somewhere at the left of the root node. It is also less than the value (22) of the direct left node of the root node. So it is going to be positioned somewhere at the left of the node with 22. But it is greater than the node with 10. Therefore, 16 is going to be to the right of the node with 10.

This trend continues until all data values have been rightly positioned.

PS: A binary tree is a data structure in which each node cannot have more than two nodes directly attached to it.