Data Structures and Algorithms

Introduction

Among all the words that a software developer/engineer is afraid of hearing, Data Structures are definitely one of the most terrifying ones, because this subject it's really tough and difficult, and many people try to avoid them as much as possible. Although, Data Structures are the real basement that forms a good software developer/engineer. When you have a well structured knowledge in this subjects, you increase the effectiveness of your code, you have a clear vision of the n different ways of solving a problem, the worst/best cases to use, and switching from one language to another becomes easier.

I have been studying a lot Data Structures, and honestly I will never stop, because there is always something to learn and improve, specially because it's a very wide field, and you would need years of study to cover every topic.

Thus, during my study path I created many summaries and notes for myself, then I compiled them all in this article, it's a little bit long, but contains a lot of information, and practical examples.

To give a summary about this article, first we will cover some programming concepts widely used in data structures study, like recursion, then we will check the different data structures usage, and some algorithms mainly used on trees (DFS, BFS).

Important Thing Regarding Recursion

One important thing to remember regarding recursion, it’s that each recursive calls create another thread, and an good example about that is imagine you just have started to execute a recursive function, and this recursive function has two if statements, where within those two there is a recursion call. In the case you enter in the first if, a new thread will be created, but don’t forget the first thread, because there is still one if statement to be evaluated. This could be harmful for space complexity, imagine that for each recursion, you have the possibility of two recursive calls, so each means that each recursion call will result in two children.

In the example above, for a recursive function that has the possibility of two executions ( two if statements), if you execute it one time, it’s going to have 2 threads, if you execute 2 times it will have 4 threads, which means that the number of possibilities is the base and the exponential index the number of execution.

For example, 2 possibilities for two executions will be 2*2, 3 possibilities in 2 executions will be 3*3.

So, when building recursive functions you have to keep in mind, will my recursive function call it recursively with only one possibility or more than one?

When you call a recursive method, and when it makes another recursive call, it stops in its tracks until that call return, so which means that the execution stops, until the recursive returns something, for example, let’s say that a test of a recursive function, it’s calling itself for 3 times, since the first recursive call, the lines bellow that will only be executed after the call returns something, for example, all the recursive calls will be stopped, until some children of it returns a value, then the parent of this children may resume its execution. 

So, imagine that your recursive function get’s called a lot of times, until the deeper level of it doesn’t return something, the upper levels will stay stopped, until something is returned, for a simple linear recursive method, since the deeper level returns something, it will trigger a chain of returns, from the deeper to the top level. A good way of testing this, is with this example:

Imagine, we want to print numbers from 10 to 0 recursively, and we created the following code: 

function func(n) {
        if(n > 0) func(n-1)
        console.log(n)
    }
    
func(10) // 1,2,3,4,5,6,7,8,9,10

You will notice that this function will print 1,2,3,4,5,6,7,8,9,10 instead of the proper order, why? Because, the console.log call it’s after the recursive call, which means that until the lower level doesn’t return something, the parents will be stopped, and the deeper level to return something is the number 1, and that is why it will print 1 first. In order to correct this, you can refactor the following code to:

function func(n) {
    console.log(n)
    if(n > 0)
         func(n-1)
} 

Data Structures and Its Usage

Let's start this topic with a recommendation of one of the best YouTube channels for Data Structures and Algorithms, it's called CodeDojo, and he teaches a lot of things regarding this topic, and also how to crack coding interviews.

There are a lot of different data structures that might be suitable to many cases, while another ones not, first of all we will present a pragmatical usage for each of the data structures:

• List(Array) - If you don’t have so many elements, and you just need to group them in a list, this is the most common data structure that can help us.
• Linked(List) - The LinkedList it’s better than a common list for adding and removing items in the middle of the array, so if you have a case where you have to add/remove a lot of items from the middle of a list, you should go with that data structure.
• Stack/Queue - If you want to data structure with LIFO/FIFO capabilities, that is the choice. Although this also can be implemented using a common array, but the deletion and insertion on queue and stack are better than array.
• Heap - A heap it’s different from a stack, and it’s usually represented by a binary tree, it’s good for implementing priorities queues.
• Binary Tree - It can be used to implementing routing table in router, data compression code, implementation of expression parser and expression solvers, solve database indexing, expression evaluation.
• Hash table - The latest data structure, when you have a huge amount of data, and you have to do a lot of searches within that data, that is the best option, but still if you have a huge amount of data, but this data needs to be sorted and in a specific order, it’s better to go with binary trees. 

Java Example, Building a Tree from an array

So imagine that you have an array of integers, and you want to create a balanced tree using those numbers, the code is quite simple, just remember that recursion is your best ally, and that the direction where the child node goes, is always compared with the root value of the tree.

class Tree {


    Node root;
    
    class Node {
        int value;
        Node right;
        Node left;




        public Node(int value) {
            this.value = value;
            right = null;
            left = null;
        }
    }




    public Node recursiveInsertInTree(int value, Node currentNode) {
        if(currentNode == null) {
            return new Node(value);
        }




        if(currentNode.value > value) {
            currentNode.left = recursiveInsertInTree(value, currentNode.left);
        } else {
            currentNode.right = recursiveInsertInTree(value, currentNode.right);
        }
        return currentNode;
    }




    public void buildTree(int[] values) {
        for(int i =0; i < values.length; i++){
            root = recursiveInsertInTree(values[i], root);
        }


    }
 
}

DFS - Depth First Search

This algorithm can be used with binary trees and graphs, it basically starts from one node, and start to descend/ascend from the another node, until a value is found. It’s used a lot in games for simulation and AI, for example imagine a chess game. The root node of your three will be the current match state, and all the children the decisions that can be taken, and each decision leaves to another set of decisions. This can be used to search for a “value”, which means the best play.

There are three ways of implementing the DFS, the preorder, postorder and inorder.

The most famous one is the preorder traversal, where you initiate from root node, visit the left subtree, and right after that the right subtree. Let’s give it an example:

// Java program for different tree traversals
  


/* Class containing left and right child of current
   node and key value*/
class Node {


    int key;


    Node left, right;
  


    public Node(int item)


    {
        key = item;
        left = right = null;


    }
}
  


class BinaryTree {


    // Root of Binary Tree
    Node root;
  


    BinaryTree()
    {
        root = null;


    }
  


    /* Given a binary tree, print its nodes in preorder*/
    void printPreorder(Node node)


    {
        if (node == null)


            return;
  


        /* first print data of node */
        System.out.print(node.key + " ");


  


        /* then recur on left sutree */
        printPreorder(node.left);
  


        /* now recur on right subtree */
        printPreorder(node.right);
    }
  


    // Wrappers over above recursive functions
    void printPreorder() { printPreorder(root); }


  


    // Driver method
    public static void main(String[] args)


    {
        BinaryTree tree = new BinaryTree();


        tree.root = new Node(1);


        tree.root.left = new Node(2);


        tree.root.right = new Node(3);


        tree.root.left.left = new Node(4);


        tree.root.left.right = new Node(5);


  


        System.out.println("Preorder traversal of binary tree is ");
        tree.printPreorder();
    }
}

If we have a tree like this:

This piece of code will print: 1, 2, 4, 5, 3, and why is going to print only the left guys first? Simply because here we come again with how recursive functions work, remember that a recursive call stops in the exactly point, until the children execution returns something, which means that a parent that started the recursion, will only resume its execution, when all their children have returned something.

So, in this case 1 will be printed first because it’s the root, and a recursion in chain will be executed until the node 4, which will be the first to return something, and them the execution on the node 2 will be continued and the node 5 will be printed, until everyone has returned something, and the root 1 can continue its execution and call the right subnodes. The name is DEEP, because as we saw, it goes until the deep level of the left first, and just after that go to the deeper on the right. 

BFS - Breath First Search

Different from the DFS, the BFS will search a value in the levels of a tree, so it will first search in root, then after that will go and search all values in the second level of the tree, and so on.

For example, if we have this tree: 

It will first search on root (1), then will go to the second level (2,3) and then on the third level (4,5).

This is useful it you are trying to find the shortest path from the starting vertex to a given vertex. It can be used to find the neighbour nodes in peer to peer networks like torrent, GPS systems, social media like finding people using your user as the root of the tree.

A code for this would be: 

// Recursive Java program for level order traversal of Binary Tree
  


/* Class containing left and right child of current
   node and key value*/
class Node


{
    int data;


    Node left, right;
    public Node(int item)


    {
        data = item;
        left = right = null;


    }
}
  


class BinaryTree


{
    // Root of the Binary Tree
    Node root;
  


    public BinaryTree()


    {
        root = null;


    }
  


    /* function to print level order traversal of tree*/
    void printLevelOrder()


    {
        int h = height(root);


        int i;


        for (i=1; i<=h; i++)


            printGivenLevel(root, i);
    }
  


    /* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
    int height(Node root)


    {
        if (root == null)


           return 0;


        else
        {
            /* compute  height of each subtree */
            int lheight = height(root.left);


            int rheight = height(root.right);


              


            /* use the larger one */
            if (lheight > rheight)


                return(lheight+1);
            else return(rheight+1);


        }
    }
  


    /* Print nodes at the given level */
    void printGivenLevel (Node root ,int level)


    {
        if (root == null)


            return;
        if (level == 1)


            System.out.print(root.data + " ");


        else if (level > 1)


        {
            printGivenLevel(root.left, level-1);
            printGivenLevel(root.right, level-1);
        }
    }
      


    /* Driver program to test above functions */
    public static void main(String args[])


    {
       BinaryTree tree = new BinaryTree();


       tree.root= new Node(1);


       tree.root.left= new Node(2);


       tree.root.right= new Node(3);


       tree.root.left.left= new Node(4);


       tree.root.left.right= new Node(5);


         


       System.out.println("Level order traversal of binary tree is ");
       tree.printLevelOrder();
    }
}

Finally...

This article is being longer than I thought, because it's so much content to present, and still there are so many things to talk about. In this article, I decided to focus on trees, because it's one of the most used data structures in screening processes for big companies like Google, Amazon, Microsoft, although many software engineers seldom don't use it.

I will make a second and third part, focusing on graphs and stacks/heaps respectively, hope everyone enjoyed this content! If you have anything to add, or to comment, just reach me out. Besides, if this article helped you or you simply liked it, give it a like, share it and show to your friends!

Thanks a lot! And take a look on my GitHub !