[Learning DSA series!] Trees: PreOrder Traversal

So, I was starting to get pretty bored of those standard array based questions. Graphs and trees seem mysterious and interesting. I don't want to pretend that this is a tutorial. It's not even close.

I'm just going to describe what I learn, my experiences, where I struggled and what not. If anyone at all is reading this, you will probably get some doubts cleared, if our doubt seems to match, and also get a sense that CS is hard. A lot of people online cast an image of being natural geniuses, and so-called "normies" like us feel like we can never catch up. It's mutual. I just want the guy struggling with trying to master coding like me, to feel better, and know that it's hard for everyone and not just for them. And, prolly share the fascination and interest in coding.

As CarryMinati would say "Shuru karte hain bina kisi bakchodi ke":

First, some terminology.

Tree: A data structure consisting of interconnected nodes (data points), like the root system of a tree.

Root: The topmost node of a tree, which has no parent (a node above its level to which it is connected).

Leaf node: A node with no children (nodes below its own level which are connected to it)

Binary Tree: A tree where each node has at most two children. A node can have none, one or two children.

So, let's get on with implementing our binary tree code. This is already given in the HackerRank question, you don't have to type this, but nevertheless it will be a good exercise to try and write one ourselves.

If you are not very comfortable with OOP, I'll try to make it as digestible as possible.

Let's start with the Node class. A class consists of some data (which can be of differing types) and some functions (called methods). Each node has 3 data components:

• info: the type has to be fixed for certain languages like C++, although there are ways to generalize the data types in C++. Might want to look up Template Specialization. This is not a problem at all in Python, where data types are implicit. For our purposes, we will keep it at int or float values.
• reference to left node
• reference to right node

The node class does not need any methods. Let's code this.

class Node:

    def __init__(self, info):

        self.info= info

        self.left = None

        self.right = None

Remember that a constructor is the function which initializes a new object of the class, and we can use this to assign some values to our class data. In Python, __init__ function designates the constructor.

Every method in a Python which messes with class data has to have a "self" parameter, which is a reference to the self. This is passed automatically while initializing a new object, and we don't need to pass it manually. This is something exclusive to Python.

Now lets get to our BinarySearchTree Class. This class will contain only one data point: a ROOT node. This node will be the start of our tree. It will be an object of the Node Class we just made. What's important here is the method we are going to make to populate a tree with values.

This is a binary search tree. This means, there are two children to each node (left and right child) and the left child will store a value smaller than the parent node, and the right will store a value greater than the parent node. Let's code this:

class BinaryTree:

    def __init__(self):

        self.root = None

    def create(self, val):

        if self.root == None:

            self.root = Node(val)

        else:

            current = self.root

            while True:

                if val < current.info:

                    if current.left:

                        current = current.left

                    else:

                        current.left = Node(val)

                        break

                elif val > current.info:

                    if current.right:

                        current = current.right:

                    else:

                        current.right = Node(val)

                        break

                else:

                    break

Ok. Let's explain the create() method. If the root has not yet been given a value (empty tree) then give it a node with the given value (val). If the tree is already populated, compare val with the value of the current node (the first time it will be the root). If the value in the current node is greater than val, we need to go left. If there is no left child, we make one. If the left child already exists, then we set current node to be the left child and repeat the process of comparing val with the current node (which is now the left child). We do the same with the right side case too. This will ensure we go to a node which needs a child to accommodate the new val, but doesn't already have one. Then, we make the node there (which is the appropriate spot due to all the discussion so far) and we are done!

Now after all this, let's get to the problem itself. It asks us to print out the elements in a depth first order, preferring the left hand side (hence the "preoder" traversal). Depth first means that we go as far as possible taking left. When we reach a node where we can no longer go any further by turning left, we explore all the paths taking one right at a time bottom to top. Maybe this program I made in Python using graphics.py can help:

So we are going to go for a recursive approach. The first thing we do, the print the info value of the current node. Then we check if the node has a left child. If it does, we recursively call the same function for currentNode.left. Then, we check if the right child exists. If it does, we send currentNode.right in another recursive call. We exit the function if there are no children to a node (i.e. leaf node).

Here is the code:

def preOrder(root):

    print(str(root.info), end = " ")

    

    if root.left != None:

        preOrder(root.left)

    if root.right != None:

        preOrder(root.right)

And that's all for now. Phew. Super long article. We will explore more trees in the next one! Until then...

[TLE fix] Pairs

This question is just as one would expect it. The first thought you get to solve it will probably be the right one.

For each element arr[i], we search for arr[i] + k in the array, and whenever it is found, we increment a counter variable.

But the twist here is that arr.index() is linear search, and is an O(n) function. Since we are putting this in a loop, the naive O(n²) solution gives a TLE.

Enter the bisect package. To use it we have to add this line at the top of our code:

from bisect import bisect_left

What does this do? Gives us binary search out of the box.
The bisect package contains 2 particularly useful functions:
bisect_left(array, element) returns the index of leftmost occurrence element in array.
bisect_right(array, element) returns the index of rightmost occurrence element in array.

Binary search is an O(logn) algorithm. Therefore our solution is O(nlogn) and it now passes all the testcases.

Note that the array must be sorted in order for binary search to work. So before calling bisect_left, we must sort the array.

[deceptively nasty] Palindrome Index

This problem is prima facie really easy looking. But its a snake waiting to bite!

What I did initially was to initialize two variables, i = 0 and j = len(s) - 1 (start and end of s).
On each iteration of a while loop (while i < floor(len(s) / 2)), compare values s[i] and s[j] and if they are equal, we are good.

But if they are not equal, one of the two things can occur. Either s[i] must be the odd letter, or s[j]. For this the natural approach is to check the next letter, and see if they match, that is:

1. compare s[i + 1] and s[j]
2. compare s[i] and s[j - 1]

If 1. is true, then s[i] must be removed, and if 2 is true, s[j] must be removed.

Easy, right?
WRONG!

Consider the following testcases:

cwwcw
wcwwc

The above logic will give the wrong output for these cases.

It turns out, conditions 1. and 2. are NOT sufficient for determining which letter is the odd one out. We must also check the next pair of elements as well. The correct conditions are:

1. if s[i] == s[j - 1] and s[i + 1] == s[j - 2]
2. if s[i + 1] == s[j] and s[i + 2] == s[j - 1]

These correctly determine which out of s[i] and s[j] is the odd one out. Deceptively nasty indeed!

[a little intuition] Max Min

Sometimes, one must trust one's intuition. In coding problems, intuition is a really useful thing to build.

When I opened this problem, I had no idea whatsoever how to approach this problem.

Suddenly a random thought popped into my head:
What if I sorted the array, and took the first k elements?
Immediately I could think of counterexamples to disprove this notion.

1, 10, 11, 12, 13 and k  = 3

But all was not lost. We could still improve upon this. What if we looked at k length contiguous subsets of this?

1, 10, 11 | 10
10, 11, 12 | 2
11, 12, 13 | 2

And eureka! We could find the minimum difference this way.

Eureka indeed. Why does this work? If you remove all the contest pressure I had, it is plain that if the array is sorted, the difference between consecutive elements is the smallest possible, while still being non-negative. For a valid contiguous subset, we are finding the sum of the differences between consecutive elements (a bit of a mouthful there).

If the consecutive differences are minimum, then the cumulative difference between the first and last elements (min and max) is minimum, and that, solves the problem.

[incremental progress :)] The Full Counting Sort

The first medium level question in my HackerRank journey! And yes, it was pretty hard for me. But the logic was easy to think of. Just hard to implement.

This was a higher level version of Jim and the Orders (whose solution is available here: https://teamresurgence.blogspot.com/2020/05/new-concept-jim-and-orders.html).

Here too, the Hashmap came in handy. Ultimately we have to sort the strings by their keys. But here we have to set it up to make the sorting "stable" (read the question). So here is what I came up with:

1. Accept the string, and it's key. Search for the key in an array called "takenKeys", which stores all the unique keys so far. If the key is found (meaning it is a duplicate), we will modify it to ensure stable sorting. Here they have put loophole of replacing the first half of strings by '-'. While accepting the strings itself, check if the the index of the loop which is accepting the strings is smaller than floor(n / 2) and simply append '-' instead of the accepted string in that case. A literal loophole!

2. This "modification" is simple. For each unique key, I have a "factor" (all these factors for each key are stored in a different array)  The factor for each key is initialized to 0.1. Whenever a duplicate key is detected, say 4, I add the factor to it. (4 -> 4.1) and then factor = factor + factor/10000. Why 10000? I actually tried, 2, 10, 100, 1000, 10000. 10000 managed to pass all the testcases. This happens because lower values can "overflow". Meaning the sums of factors can add up to a value larger than 1. If 4 becomes 5 or more, instead of 4 < x < 5, then our sorting will mess up.
So if our keys were originally like this:
1, 3, 0, 1, 0, 1
they now become (if factor = factor + factor / 10, for simplicity):
1, 3, 0, 1.1, 0.1, 1.11
After sorting:
0, 0.1, 1, 1.1, 1.11, 3
Now it should be clear why the sorting is stable.

3. Now send this dictionary, with keys being the modified keys and the values being associated strings. Sort the dictionary by keys (unlike Jim, where we sorted by values). And now, print the values!

[playing with combinations] Smart Number

A very interesting problem, leading to a result that seems counter intuitive till you prove it. The difficulty is that intuition doesn't encourage one to try and prove it.

Consider any number n.
It has prime factors having varying powers, and those powers may be odd or even
After squaring, all the powers will become even. Let the power be p, therefore there are p + 1 ways to put that prime
in our factor prime^(0, 1, 2, ... p). Therefore the number of factors of any number are:
(p1 + 1)(p2 + 1)... so on
But since p is always even, p + 1 is guaranteed to be odd.
Since a product of odd numbers is always odd, the number of factors is odd.

Therefore, a perfect square will always have odd number of factors.

[new concept] Jim and the Orders

This problem becomes really easy if we use a hashmap.

The Hashmap:
A data structure very much like an array, but the "index" of this array can be any data type. This "index" is called "key". The data associated with each key is called its "value".
For example:
"Key1" : 1023
"Key2" : "Hello"
12.13 : True

An advantage of hashmap is that the time required to extract a value given it's key is constant (O(1)).

In python, hashmaps are called "dictionaries".

For this problem, I created a dictionary with the keys being natural numbers, representing the position of each customer in the line (1, 2, 3, ...) and the value being the time for serving the order.

Then I sorted the dictionary by value. The keys should now be in correct order!
One way to do it in python is this:

sorted_keys = sorted(dict.items(), key = lambda kv:(kv[1], kv[0]))

This returns an array of tuples (key, value) of the dictionary sorted by value.

Just extract the keys part in a separate array, and return it.

[a delightful little problem] Fair Rations

This is a complex sounding problem that is actually very simple, and yet requires some creativity to solve.
Let's consider an array, with elements being boolean (True if the number of loaves with the person in that index in the line is even, else False). A typical starting array may look like this:

TTTTF

Now this case is interesting. We observe that in order to eliminate F entirely, we must have a situation with two nieghboring F's. Then we can give one loaf to both, and convert them to T. Hence, the total number of F's must be even, otherwise a solution is not possible, in which case we return "NO".

Now let's look at some examples cases where it is possible:

1. TFTFT

2. TTFFT

3. FTTTF

I tried some experimentation, and came up with this algorithm to distribute the loaves:

1. Loop through every element. If that element is T, move on.
2. If that element is F, then invert that element and the element to its right. Increment a "breadCount" variable by 2 everytime we do this.
3. Continue doing this. By the end of this, we must end up with all T's.
4. Return the "breadCount"

Also: Solution accepted on first try :))

[edgy question!] Lisa's Workbook

This problem is a genuinely good one. It requires unbiased and patient consideration of all the possible edge cases.

Solution:
If we write down a few examples, we sense intuitively that we need to keep track of a few things in for every chapter.

We need to keep track of:

• The current page number
• The number of pages required by each chapter
• The question numbers on each page

The number of pages required by the i'th chapter is equal to ceil( arr[i] / k ) by observation.

I feel just putting the code would be the best idea for this one. The basic principle is while keeping track of those 3 things, we loop through all the question numbers of a given chapter, incrementing "page" whenever question number exceeds limit for each chapter, and moving to the next chapter when the number of questions in that chapter is over.

Implementation is slightly tricky so I'll just post my code for this one:

def workbook(n, k, arr):

    special = 0

    page = 1

    for i in range(len(arr)):

        finalpage = page + math.ceil(arr[i] / k)

        j = 1

        offset = 0

        while True:

            if j > k:

                page += 1

                j = j - k

                offset += k

            if page > finalpage:

                break

            if (j + offset) > arr[i]:

                break

            if (j + offset) == page:

                special += 1

            j += 1

        page = finalpage

    return special

Pretty good!
But my friend Tejas Rao made it even easier:

def workbook(n, k, arr):

    b = list()

    c= 0

    pg = 1

    for i in range((n)):

        x = arr[i]

        for j in range(1,x+1):

            print(j,pg)

            if j==pg:

                c+=1

            if j == x:

                continue

            if j%k ==0:

                pg+=1

        pg+=1

    return c