Search code examples
algorithmbinary-search-treesequences

Find valid sequences in Binary search trees

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.

Solution

  • 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)":

    tree for sequence A

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

    enter image description here

    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 ]