[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...