BST Sequences in Python

# start background

I embarked on a journey to skill up in the domain of programming about 2 years ago, and I started out doing tutorials on Codecademy as well as signing up with courses on Udemy. As my work involved quite a bit of travel, I downloaded the tutorials offline into my ipad and studied on the plane. I started out with the intention of learning programming to build useful things, and even though the journey was really tough at every step, I realised that I never knew what the word ‘difficult’ really meant until I immersed myself into data structures and algorithms.

I am a major in Aerospace Engineering, graduated First Class Hons from Singapore. After that I joined Schlumberger as a New Products Engineer, working on oilfield pumps and had stints in in the North Sea installing equipment. Hours were long (16 hour days were common, with weekends usually burnt too), pay was low but the experience was amazing, and I would not trade that for anything else. Till today the survival training doing capsize drills and going down a Norwegian escape chute as well as taking the helicopter to the rig are fond memories, not something people would experience unless they are an oilfield engineer.

After that I joined P&G as a researcher working on Hair Care brands, after 2 promotions I started to realize that whilst project management, stakeholder management (making sure everyone you’re working with is happy) and establishing credibility might be important, and actually is the most important anywhere, I was not gaining skills on the job which are required to do what I am super passionate about, which is to ideate, build useful things that solve problems and set up a brand. This led me to pick up programming to create a scraping and data mining tool for the masses, and this tool has been providing valuable consumer insights to teams working on billion dollar brands like Pantene, Vicks, Tide, Head and Shoulders, SKII, Oral b, etc. The tool is called www.wheregottext.com. (WGT)

Other than WGT, I have been building a job hunting app and an app for recognising products in the supermarket and showing relevant online ratings and reviews from other consumers so that consumers can make a more informed decision before buying, instead of just talking to the sales reps in the stores, among other things. I have also been involved in Android and iOS app development, which I shall describe another time. I am doing these activities partnering with a brilliant coder and close friend who I met in College, and a brilliant marketer and also close friend who I met in my first job. Coding and marketing are not our day jobs.

Anyway, enough with the ranting and I will leave more introduction to another post. Till now, one of the more difficult problems I have come across is the question: Given a BST, find a list of lists which can make the BST.

# end background

I shall use the example in Cracking the Coding Interview by Gayle Laakmann McDowell to provide my perspective and explanation in hopes that people coming across this problem would not struggle as much as I did when I was trying to find useful explanations online, with no success. I will provide the code in Python. The code in the book is written in Java.

Consider the binary search tree on the left. We can try to manually list some of the possible arrays that contains elements that could be inserted to form the binary search tree.

[20,10,5,15,25]

[20,10,25,5,15]

[20, 25,10,15,5]

…

Notice that for every subtree (consisting of three nodes) the root must always be inserted first, followed up any order of the children, because the children are at the same level.

My initial though to solve this problem is to first do a pre-order traversal of all the nodes, and store the nodes into a list. I would then generate a list of lists of all permutations of the elements, thereafter filtering out lists starting with the value 20, and also the condition of 10 coming before 5 and 15 (since 10 must be added first to form the BST). There are many flaws with this thinking. This is a very manual method and if the BST is bigger or if we are not able to visualise the BST in a chart as above, it would be unnecessarily complex to figure out the hierarchy of nodes. We could do a BFS and figure out that 10 must be before 5 and 15, but I would rather follow the textbook method than to implement this.

We know that we always break down the problem into smaller ones, and then for BSTs we could use recusion to expand a solution to a bigger problem. In the book, two recursion functions are being used. One is called weaveLists, and another is called allSequences which calls weaveLists.

First of all, let’s define a Tree class. We need to be able to do insertions and also to get the root.

class Node:    def __init__(self, val):        self.l = None        self.r = None        self.v = val

class Tree:    def __init__(self):        self.root = None

def getRoot(self):        return self.root

def insert(self, val):        if(self.root == None):            self.root = Node(val)        else:            self._insert(val, self.root)

def _insert(self, val, node):        if(val < node.v):            if(node.l != None):                self._insert(val, node.l)            else:                node.l = Node(val)        else:            if(node.r != None):                self._insert(val, node.r)            else:                node.r = Node(val)

Thereafter, we want to be able to weave the elements of a subtree. The weaveList function is as follows (I added in comments directly into the code to explain what is happening) :

# Note that in the recursion, we are always using the same reference to first, second and prefix lists, and hence operations to modify these lists would have to be done in-place. Any copies would have to be done with the deepcopy function.

### EDIT TO CODE BELOW: instead of using result = prefix.copy(), use:

import copyresult = copy.deepcopy(prefix)

Since .copy() is a shallow copy.

Thank you to Zhi Yong for pointing that out.

# 'first' list shall be referred to as first[]# 'second' list shall be referred to as second[]# 'prefix' list shall be referred to as prefix[]

def weaveLists(first, second, results, prefix):    # if first or second is an empty list    if not first or not second:        # ensuring that result is a CLONE and not a reference to prefix        result = prefix.copy() ### EDIT HERE TO DEEPCOPY        # add result to first or/ and second lists        if first:            result += first        if second:            result += second        # append the weaved list which is result, to results        results.append(result)        return

        # add result to first or/ and second lists        if first:            result += first        if second:            result += second        # append the weaved list which is result, to results        results.append(result)        return

    # this would be the method as described in the textbook    # first, remove and store first element of first[]    headFirst = first.pop(0)    # append to prefix    prefix.append(headFirst)    ### add recursive call to operate on first[]    weaveLists(first, second, results, prefix)     # exit when first[] is empty

    # reset prefix for second recursive call below by removing last element    # IMPT to modify in-place    del prefix[-1]     # reset first[] for second recursive call below by adding back first element    # IMPT to modify in-place    first.insert(0,headFirst)

    # do the same thing on the second[]    headSecond = second.pop(0)    prefix.append(headSecond)    ### add recursive call to operate on first[] and second[]    weaveLists(first, second, results, prefix)    del prefix[-1]    second.insert(0,headSecond)

We want the weaveList function to operate on subtrees and build up to the entire Tree.

Hence, in general we would want weaveList to work on subtree 1 which is in blue, then the entire tree which is green.

The code for allSequences is hence (with comments for explanation):

def allSequences(node):    # this is the final list of lists we want to output    results = []    # termination, append [] so that results will not be empty\    # and the nested for loop will still execute since    # leftSeq == [[]] and rightSeq == [[]] in termination    if not node:        results.append([])        return results

    # prefix will always be root of subtree    prefix = []    prefix.append(node.v)    # then represent the left and right subtrees    leftSeq = allSequences(node.l)    rightSeq = allSequences(node.r)

    # nested for loop and call weaveLists on each list in    # leftSeq and rightSeq, which are list of lists    # and each represents results of each subtree    for left in leftSeq:        for right in rightSeq:            # make weaved an empty list,             # which is results in weaveList            weaved = []            weaveLists(left, right, weaved, prefix)            # weaved is list of lists generated by left[] and right[]            # add weaved list of lists to final             # results list of lists            results += weaved

return results

The main function to drive the program would be:

if __name__ == "__main__":

    tree = Tree()    tree.insert(20)    tree.insert(10)    tree.insert(25)    tree.insert(5)    tree.insert(15)

    allSeq = allSequences(tree.getRoot())

    for each in allSeq:        print (each)    print (len(allSeq))

Copy all the code into one single script and run it to see results. The code is in Python3.

Feel free to reach out for any comments, advice or questions.

BST Sequences in Python was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.