Question

Using Binary Search Tree implementation, what would the resulting 'table' look like after inserting key/value pairs: (a, 1), (x, 5), (m,19), (b, 3), (f, 8).

Answer 1

The problem involves insertion into a binary search tree (BST). Insertion is dependent on the values of the keys.  A BST is a binary tree where each node has a key (and possibly an associated value) and satisfies the conditions: 1. The key in any node is larger than all the keys in nodes in its left subtree. 2. The key in any node is smaller than all the keys in the nodes in its right subtree.

Now considering the values of the keys i.e. a, x, m, b, f in the given order.

1. a is the first node

2. x is added to the right subtree of a since x is greater than a

3. m is added to the left subtree of x since m is smaller than x

4. b is added to the left subtree of m since b is smaller than m

5. f is added to the right subtree of b since f is greater than b

See the image below to verify that property of a BST holds always for all the nodes. eg. all elements greater than a are in its right subtree, similarly all elements lesser than x fall in its left subtree.