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

Intuition:

If sequence[i] > sequence[i+1] , path had searched in the left sub tree and the next elements in the sequence must be no more than sequence[i]

else, the path includes elements of the right subtree and the next elements in the sequence must be no less than sequence[i]

we could use the above logic to write a brute-force solution that would give result in O(n^2) time complexity

# checks if any elements in the sequence is greater than val
def any_element_greater(sequence, val):
  for e in sequence:
    if e > val:
      return True
  return False

# checks if any elements in the sequence is lesser than val
def any_element_lesser(sequence, val):
  for e in sequence:
    if e < val:
      return True
  return False

# checks if the sequence is valid
def is_valid_seq(sequence):
  if len(sequence) < 2:
    return True
  
  prev = sequence[0]
  for idx, val in enumerate(sequence):
    if prev > val:
            # checks if the rest of the sequence is valid based on direction
      if any_element_greater(sequence[idx:], prev):
        return False
    elif prev < val:
            # checks if the rest of the sequence is valid based on direction
      if any_element_lesser(sequence[idx:], prev): 
        return False
    prev = val

  return True

Optimization:

We could use max and min variables to carry forward the valid range - memoization

def valid_sequence(sequence, i=0, m_min=1, m_max=1000):
  '''
  Checks if the Sequence is a correct path in BST
  Parameters:
    sequence: path to the data in the BST
    i: current data we are validating in the path
    m_min: data should be more than m_min
    m_max: data should be less than m_max
  Returns:
    Boolean: If the sequence is a valid path in BST
  '''
    if len(sequence) == 0:
        return True

  data = sequence[i]

  # check if data is in valid range
  if not (m_min <= data <= m_max):
    return False

  # Base case, return if we reached the end
  if i == len(sequence) - 1:
    return True

  '''
  Adjust min, max for the next data elements
  depends on the next element in the sequence
  '''
  next = sequence[i+1]
  if next > data:
    m_min = max(m_min, data)
  else:
    m_max = min(m_max, data)

  return valid_sequence(sequence, i+1, m_min, m_max)

Tests:

options = {
    '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, 292, 358, 363]
}

for option in options:
  print(f'{valid_sequence(options[option])} \t - {option}. {options[option]}')

Results:

True     - a. [2, 252, 401, 398, 330, 344, 397, 363]
True     - b. [924, 220, 911, 244, 898, 258, 362, 363]
False    - c. [925, 202, 911, 240, 912, 245, 363]
True     - d. [2, 399, 387, 219, 266, 382, 381, 278, 363]
False    - e. [935, 278, 347, 621, 299, 292, 358, 363]

Reasoning:

In option c, 912 is greater than 911 while we go into left sub-tree at 240. so it is invalid

In option e, we go right from 347 but we encounter 299 and 292 in the sequence. so it is invalid

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

Answer 3

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 ]