Question

In a binary search tree (bst), which property holds true for all nodes in the left subtree of a given node?

a. all nodes have smaller values than the given node.
b. all nodes have larger values than the given node.
c. all nodes have the same value as the given node.
d. there is no left subtree in a bst.

Answer 1

a. all nodes have smaller values than the given node. The left subtree of a node in a binary search tree (BST) contains nodes with smaller values than the given node.

Step-by-step explanation:

The correct answer is option a. all nodes have smaller values than the given node. In a binary search tree (BST), the left subtree of a node contains all nodes with smaller values than the given node. This property allows us to efficiently search for values in a BST by navigating left or right based on whether the value we are looking for is smaller or larger than the current node.

For example, consider a BST with the following structure:

5
/ \
3 8
/ \ \
2 4 9

In this BST, the left subtree of the node 5 contains the nodes with values 3, 2, and 4, all of which have smaller values than 5.