Binary Search Tree Difference

Given a binary search tree, determine the minimum difference between any two different values in it. You may assume that the BST has at least two nodes.

Implement the function bstree_difference in bstree_difference.c. This function will then be called by the main function in bstree_difference.c.

To run your solution:

$ make
$ ./test_bstree_difference

Input format

Upon running ./test_bstree_difference, the user will be prompted to provide a single line to standard input. This line should contain a space-separated list of integer values, representing the preorder traversal of the BST.

Output format

The program will write to stdout. It will print Minimum difference: followed by the return value of the call made to bstree_difference.

Sample

Input:

11 7 4 20 18 23 30

Output:

Minimum difference: 2

Explanation:

The BST is

     11
    /  \
   /    \
  7     20
 /     /  \
4     /    \
     18    23
             \
             30

and the minimum difference between any two different values in it is 20 - 18 = 2.

Assumptions

• The input list contains at least two and at most MAX_BST_SIZE values.
• Each input value is positive and can represented by an int in C.
• The number of characters in the input is at most MAX_LINE_LEN - 1.

CSE Autotest

When you think your program is working, you can use CSE autotest to test your solution.

$ 2521 autotest bstree_difference

Extra challenges

Any efficient solution, such as one that runs in O(n) or O(n log n), should pass all of the autotests, but here are some extra challenges if you're interested:

• Solve the problem using O(h) additional space, where h is the height of the BST. Hint: consider performing an inorder traversal of the BST.
• Solve the problem using O(1) additional space. Hint: think about what functionality the provided bstree_node struct offers.

Additional space refers to any space allocated between the time that the function bstree_difference is called and the time it returns.

Solution

You can view the solution code to this problem here.