BST Sequences in Python

# start background

I embarked on a journey to seriously skill up in the domain of programming 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. The environment I was immersed in though, was super great, with supportive colleagues and management. And working in that corporate setting made me realise how much there is to learn about how a company works; how management makes decisions (whether data-based or from the gut (intuition), which is why business is such a beautiful science and also an art) on allocating people and resources and integrating efforts from different departments to build and invigorate brands. Amazing stuff.

I wanted to help management and product managers at all levels of the company make better-informed decisions by providing quick and accurate facts, and 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 (acronym WGT) (I have set up the authentication so only P&G employees can create an account).

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.

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 = Noneself.r = Noneself.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 listif not first or not second:# ensuring that result is a CLONE and not a reference to prefixresult = prefix.copy() ### EDIT HERE TO DEEPCOPY# add result to first or/ and second listsif first:result += firstif second:result += second# append the weaved list which is result, to resultsresults.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 outputresults = []# termination, append [] so that results will not be empty\# and the nested for loop will still execute since# leftSeq == [[]] and rightSeq == [[]] in terminationif 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.