Tree Preorder Traversal

Good morning! It is a sunny and warm Sunday morning in the Twin Cities of Minneapolis and St. Paul. Yesterday due to high temperature and humidity concerns, my wife and I decided to start lunch earlier than usual. We finished our mid morning cup of triple espresso around 11:00 AM.

My wife made some nachos. She used small tortilla chips, and a block of Colby-Jack cheese which she shredded in the Ninja blender. For the salsa she used one or two avocados, some jalapenos from a jar and some Pace picante medium strength sauce. The plain tortillas with the cheese were placed in a 350 F oven for about 20 minutes. That melted the cheese.

While she was dealing with the nachos, I cut six potatoes to make some fries. I lit and cleaned the grill. I placed in the grill a large cast iron frying pan with some sunflower oil. When the grill reached 400 F I put 18 chicken wings in the cast iron pan, added some Goya adobo seasoning, and set an alarm in my phone for 15 minutes.

We sat down on the deck and while the grill was doing the work for us, we were enjoying the sun and a few glasses of cold Stella Artois beer. After 15 minutes I moved the wings and set an alarm for another 15 minutes. Our grill easily gets to 600 F+ degrees. When it would pass the 500 F mark, I would reduce the flow of gas so the grill would not get hotter.

We repeated the process with a second batch of 18 wings. That took another half hour or so.

When the wings were done, we put the potatoes in the same pan we used to fry the wings. No seasoning was added. The alarm was now set for 10 minutes. At that time I moved the fries in the skillet and continued to cook them for the second and last interval.

When we started with the fries, the outside temperature was in the high 80 F so we decided to keep an eye on the grill from the comfort of the air conditioned living room.

When all was done we turned the grill off and brought the chicken wings and fries into the kitchen. We added rock salt to the fries and hot sauce to the chicken wings. We tried consuming all the food, but we were not able to do so. O well, they will be part of our lunch today.

OK, enough of food. Let’s get to the main subject for this post.

Yesterday I was browsing YouTube and found some HackerRank videos indicating solutions for problems. I decided to log into HackerRank and make a quick search on tree traversals. That is how I found the Tree: Preorder Traversal problem.

On a side note, the format for the problems has improved considerably. I understand that the subject for this problem was simple but simplicity and elegance is always good.

If interested in this problem please visit the HackerRank site and read the requirements. As usual they showed the results for a tree but did not include the sample input. Note that if you enter the values for the nodes in different orders you will get different outputs.

My interest this weekend was to play with Java. In the past few weeks I have been working with Python, C and C++. It is interesting how you tend to forget things when you do not practice for a few weeks. That said; it is like riding a bicycle. As usual after a few minutes all comes back.

I decided to use VSCode from Microsoft for the IDE. Of course there are so many IDEs (i.e., Eclipse and IntelliJ IDEA) that would also work well. Lately I have been using VSCode for Java and Python. I implemented the code using one of my Windows 10 machines. In retrospect, I could have used Linux but the 4K monitor on my machine is quite large and nice.

I decided not to start by not creating an empty project on GitHub.

# **** open a new console on Windows ****
Microsoft Windows [Version 10.0.18363.959]
(c) 2019 Microsoft Corporation. All rights reserved.

# **** looked for a workspace folder for this project ****
C:\Users\johnc>dir
07/16/2020  07:39 AM    <DIR>          .
07/16/2020  07:39 AM    <DIR>          ..
05/13/2020  03:07 PM                57 .angular-config.json
06/18/2020  04:50 PM    <DIR>          .atom
05/13/2020  03:03 PM    <DIR>          .config
09/22/2019  08:00 AM    <DIR>          .eclipse
03/15/2020  08:38 AM                59 .gitconfig
06/19/2020  08:40 AM               119 .node_repl_history
04/23/2020  11:11 AM    <DIR>          .p2
05/07/2020  08:11 AM         1,005,502 .pipwin
04/21/2020  08:07 AM    <DIR>          .pylint.d
09/22/2019  08:00 AM    <DIR>          .tooling
03/10/2020  03:53 PM    <DIR>          .vscode
07/15/2020  09:12 AM    <DIR>          3D Objects
07/15/2020  09:12 AM    <DIR>          Contacts
04/08/2020  07:59 AM    <DIR>          ContainsCloseNums
02/17/2020  03:52 PM    <DIR>          Documents
07/15/2020  09:12 AM    <DIR>          Downloads
09/22/2019  07:57 AM    <DIR>          eclipse
09/22/2019  07:59 AM    <DIR>          eclipse-workspace_0
07/15/2020  09:12 AM    <DIR>          Favorites
07/15/2020  09:12 AM    <DIR>          Links
07/15/2020  09:12 AM    <DIR>          Music
05/13/2020  03:49 PM    <DIR>          my-app
09/12/2019  04:36 PM    <DIR>          NCH Software Suite
07/16/2020  07:39 AM    <DIR>          node_modules
07/18/2020  06:22 AM    <DIR>          OneDrive
07/16/2020  07:39 AM             3,871 package-lock.json
05/04/2020  03:42 PM    <DIR>          pipwin
07/15/2020  09:12 AM    <DIR>          Saved Games
07/15/2020  09:12 AM    <DIR>          Searches
05/11/2020  03:04 PM    <DIR>          source
07/15/2020  09:12 AM    <DIR>          Videos
05/05/2020  01:30 PM    <DIR>          vimfiles
06/10/2020  10:50 AM    <DIR>          workspace0
07/15/2020  07:11 AM    <DIR>          workspace1
05/05/2020  01:51 PM             3,281 _viminfo

# **** decided on this one ****
C:\Users\johnc>cd workspace1

# **** created an empty forlder for the project ****
C:\Users\johnc\workspace1>mkdir TreePreorderTraversal

# **** check if all went well ****
C:\Users\johnc\workspace1>dir
07/18/2020  09:28 AM    <DIR>          .
07/18/2020  09:28 AM    <DIR>          ..
07/08/2020  07:44 AM    <DIR>          base-syntax
07/01/2020  08:58 AM    <DIR>          HospitalsHillClimbing
06/22/2020  11:34 AM    <DIR>          learnangular5
07/09/2020  02:21 PM    <DIR>          lists-conditionals
07/02/2020  08:48 AM    <DIR>          react-complete-guide
07/15/2020  08:10 AM    <DIR>          styling-components-elements
07/11/2020  10:18 AM    <DIR>          TheMasseuse
07/18/2020  09:28 AM    <DIR>          TreePreorderTraversal

# **** changed to the new folder ****
C:\Users\johnc\workspace1>cd TreePreorderTraversal

# **** ready to start developing the code for the solution ****
C:\Users\johnc\workspace1\TreePreorderTraversal>dir
07/18/2020  09:28 AM    <DIR>          .
07/18/2020  09:28 AM    <DIR>          ..

I created and empty folder in one of the work spaces. At that time I edited a short readme file and worked on the Java code for the solution. When done I have the following on my folder for the project:

# **** after writing the code for the solution and a simple readme file ****
C:\Users\johnc\workspace1\TreePreorderTraversal>dir
07/19/2020  08:07 AM    <DIR>          .
07/19/2020  08:07 AM    <DIR>          ..
07/18/2020  09:38 AM               358 README.md
07/19/2020  08:06 AM             3,600 Solution.java

Before we moved the code to GitHub let’s see how I went about developing it.

I went to Wikipedia and found an article on preorder tree traversal. You can search for existing code on-line or you can also look existing code in your workspaces. I know I have code and posts in my blog on this subject, but decided to just rely on Wikipedia.

6
1 2 5 3 6 4
main <<< t: 6
main <<< data: 1
main <<< data: 2
main <<< data: 5
main <<< data: 3
main <<< data: 6
main <<< data: 4
1 2 5 3 4 6
1 2 3 4 5 6
4 3 6 5 2 1

The program provided by HackerRank expects a number with the count of nodes followed by a line with the actual node values. As I mentioned before, if you enter the same values in different order your results may vary. When done, just give it a try and see if you can explain why the difference in output.

I always like to understand how the data is presented. For this exercise I display the data to make sure all is well. As we will see, the code for collecting the data was provided by HackerRank. I just added some comments and displayed the values. The logic was not altered.

Also note that the final program displays three lines. Of interest for this project is the first line. The other two lines are bonus output which will cause your solution to fail.

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {

        // **** open a scanner ****
        Scanner scan = new Scanner(System.in);

        // **** read the number of nodes ****
        int t = scan.nextInt();

        // ???? ????
        System.err.println("main <<< t: " + t);

        // *** define the root of the binary tree ****
        Node root = null;

        // **** loop inserting nodes into the binary tree ****
        while (t-- > 0) {

            // **** get the data for the next node in the binary tree ****
            int data = scan.nextInt();

            // ???? ????
            System.err.println("main <<< data: " + data);

            // **** insert the node into the binary tree ****
            root = insert(root, data);
        }

        // **** close the scanner ****
        scan.close();
		
       // **** pre-order traversal ****
        preOrder(root);
        System.out.println();

        // **** in-order traversal (optional) ****
        inOrder(root);
        System.out.println();

        // **** post-order traversal (optional) ****
        postOrder(root);
        System.out.println();
    }	

The test scaffolding is simple and short. We open a scanner to read input. We start by reading the number of nodes. We display the value to make sure we understand how the code works.

We then create the root for our tree. A null value is needed because the tree is empty.

We read the values and insert them as nodes int our tree. The insert code was also provided by HackerRank. When done we close the scanner and call the preOrder function. The rest of the testing code is out of the scope of this problem.

/**
 * 
 */
class Node {
    Node left;
    Node right;
    int data;
    
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

The Node class is simple. We have a left and a right child and a value for the node. Only a constructor method is available.

    /**
     * Function provided by HackerRank.
     * This is a recursive function.
     */
    public static Node insert(Node root, int data) {
        if (root == null) {
            return new Node(data);
        } else {
            Node cur;
            if (data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }

The insert method is also provided by HackerRank. You probably want to take a look at it to understand how it works. Note that this code is recursive. The first time called it just takes of the root for the tree. When you are past that point, it calls it recursively to look for a place in the tree and then create and insert the new node with the specified value.

    /**
     * Function we need to develop.
     * This is a recursive function.
     */
    public static void preOrder(Node root) {

        // **** check if we are done ****
        if (root == null)
            return;

        // **** display the data in this node ****
        System.out.print(root.data + " ");

        // **** traverse the left child ****
        preOrder(root.left);

        // **** traverse the right child ****
        preOrder(root.right);
    }

This is the preOrder traversal code. It checks if done. Otherwise it displays the value and then recursively keeps on calling it until the left branches are traversed. It then recursively calls itself on the right branch. The simplest way to understand it is to experiment with a single node and then add a node at a time to understand the logic.

   /**
     * Optional function to perform in-order tree traversal.
     * This is a recursive function.
     */
    public static void inOrder(Node root) {

        // **** check if we are done ****
        if (root == null)
            return;

        // *** visit the left child ****
        inOrder(root.left);

        // **** display the data in this node ****
        System.out.print(root.data + " ");

        // **** visit the right child ****
        inOrder(root.right);
    }

This is optional code. The inOrder traversal function does a traversal of the tree in a different order. It first visits the left child, then prints the value of the node and then visits the right children. It contains exactly the same code as in the preOrder method but arranged in a slightly different order. As before take time stating with a single node, add one node at a time and make sure you understand the logic.

    /**
     * Optional function to perform post-order tree traversal.
     * This is a recursive function.
     */
    public static void postOrder(Node root) {

        // **** check if we are done ****
        if (root == null)
            return;

        // **** visit the left child ****
        postOrder(root.left);

        // **** visit the right child ****
        postOrder(root.right);

        // **** display the data in this node ****
        System.out.print(root.data + " ");
    }

This is also optional code. The postOrder traversal function does a traversal of the tree in a different order. It first visits the left branch, then the right branch of each node and then prints the value of the root.  It contains exactly the same code as in the preOrder and inOrder methods but arranged in a slightly different order. As before take time stating with a single node, add one node at a time and make sure you understand the logic.

# **** opened a new console window ****
Microsoft Windows [Version 10.0.18363.959]
(c) 2019 Microsoft Corporation. All rights reserved.

# **** changed to the workspace with the folder holding the solution ****
C:\Users\johnc>cd workspace1

# **** verified that we are in the proper workspace ****
C:\Users\johnc\workspace1>dir
07/18/2020  09:28 AM    <DIR>          .
07/18/2020  09:28 AM    <DIR>          ..
07/08/2020  07:44 AM    <DIR>          base-syntax
07/01/2020  08:58 AM    <DIR>          HospitalsHillClimbing
06/22/2020  11:34 AM    <DIR>          learnangular5
07/09/2020  02:21 PM    <DIR>          lists-conditionals
07/02/2020  08:48 AM    <DIR>          react-complete-guide
07/15/2020  08:10 AM    <DIR>          styling-components-elements
07/11/2020  10:18 AM    <DIR>          TheMasseuse
07/18/2020  09:34 AM    <DIR>          TreePreorderTraversal

# **** moved to the folder holding the code for this solution ****
C:\Users\johnc\workspace1>cd TreePreorderTraversal

# **** initialized a git repository in my machine ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git init
Initialized empty Git repository in C:/Users/johnc/workspace1/TreePreorderTraversal/.git/

# **** check what happened (all as expected) ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git status
On branch master

No commits yet

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        README.md
        Solution.java

nothing added to commit but untracked files present (use "git add" to track)

# **** add the files to git ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git add .

# **** check that all is as expected ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git status
On branch master

No commits yet

Changes to be committed:
  (use "git rm --cached <file>..." to unstage)
        new file:   README.md
        new file:   Solution.java

# **** commit the code and the README.md file ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git commit -m "first commit"
[master (root-commit) 1d01044] first commit
 2 files changed, 162 insertions(+)
 create mode 100644 README.md
 create mode 100644 Solution.java

# **** check that all is as expected ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git status
On branch master
nothing to commit, working tree clean

# **** after creating an empty git repository on GitHub
#      I got the path to it so I can make use to make a remote copy ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git remote add origin https://github.com/JohnCanessa/TreePreorderTraversal.git

# **** check on the name of my current remote repository ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git remote -v
origin  https://github.com/JohnCanessa/TreePreorderTraversal.git (fetch)
origin  https://github.com/JohnCanessa/TreePreorderTraversal.git (push)

# **** push or code to the specified repo ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (4/4), done.
Writing objects: 100% (4/4), 1.29 KiB | 1.29 MiB/s, done.
Total 4 (delta 0), reused 0 (delta 0), pack-reused 0
To https://github.com/JohnCanessa/TreePreorderTraversal.git
 * [new branch]      master -> master

# **** check if all is well ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git status
On branch master
nothing to commit, working tree clean

# **** check the log ****
C:\Users\johnc\workspace1\TreePreorderTraversal>git log
commit 1d0104430518cf71407eb60df991ad25d67a645a (HEAD -> master, origin/master)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Sun Jul 19 08:08:21 2020 -0500

    first commit

OK, the code has been completed and it seems to work. I know the code for this problem works because it was accepted by HackerRank. I will get back to the other two methods shortly.

Instead of first creating a GitHub repository with a README.md file, I worked on the code and then will create just the remote repo on GitHub.

I started by initializing git in the directory the code was created. We add the two files we have created. We commit the code. At that point I went to GitHub and created an empty repository. We need to do this because we need the URI to pass to git on our machine.

Once we have the URI for the repository in GitHub we add the remote origin. We then check that we have properly set the remote git repo. We push the contents of our local git repo to the remote one in GitHub. We perform a couple checks which indicate all is well. At this point you can go to GitHub and verify that the two files are there.

In the code for this post I added a couple tree traversals that were not part of this problem. We can verify they generate the expected output; and they do. That said, I searched HackerRank and found two more challenges each requesting the code we created as a bonus in this post. I copied it and ran the checks. Both were accepted.

I will see if I have time for another HackerRank problem.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1,426 subscribers to my blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.