Find valid sequences in Binary search trees

Question

It is assumed that the integers between 1 and 1000 are arranged in a binary search tree, and it is desired to find the number 363. Some of the following sequences, which could not be the sequence of nodes traversed?

a) 2, 252, 401, 398, 330, 344, 397, 363 ;

b) 924, 220, 911, 244, 898, 258, 362, 363 ;

c) 925, 202, 911, 240, 912, 245, 363 ;

d) 2, 399, 387, 219, 266, 382, 381, 278, 363 ;

e) 935, 278, 347, 621, 299, 392, 358, 363.

Is it necessary to make patterns? Write in a minimal form property to check. Thanks.

Answer 1

Go here: https://www.cs.usfca.edu/~galles/visualization/BST.html put in each number one at a time in the top left, next to 'insert', and click 'insert'. It will build a binary tree as you enter numbers.

Do that for each of the sequences and compare how they look.

This is the route through "a)":

It's a single chain. This is the attempted route through "c)":

It's not a single path from top to bottom, it has a wrong-turn offshoot. You wouldn't take a wrong turn if 363 was in the tree and you were just going directly to it.

In c) 911 splits left on 240 and right on 912.

In e) 347 splits right on 621 and left on 299.

They can't be the sequences traversed on the way to 363, because one of the nodes in each list isn't on the way to 363.

[Screenshots taken from https://www.cs.usfca.edu/~galles/visualization/BST.html ]

Answer 2

range [min,max] - initialize to [1,1000]

key - target key to be searched

seq[1,N] - sequence of numbers in the binary search tree

The idea is to keep track of the valid range [min,max]. Initially all numbers 1 through 1000 are in range. If you encounter a node with key say 2 and your target is 363, you would take a right turn. As you are taking a right turn, any key you will encounter in this subtree should be greater than 2. So you update the min in range to be 2. Now your range is [3,1000]. When you encounter 252, the range becomes [253,1000]. At 401, you take a left turn so all the keys in the subtree has to be less than 401. So you set the max to 400 it becomes [253,400].

Now at any point in the sequence, you need to check if the value is within the range. If not then there is a violation. If the key matches, then it has to be the last number in the sequence.

Here is the pseudocode

boolean validate(seq[1,N],key,range)
    for i from 1 to N
        if(seq[i] < range.min || seq[i] > range.max)
            return false
        if(key < seq[i])
            range.max := key-1
        else if(key > seq[i])
            range.min := key+1
        else
            return i=N
    return true