Journey to Become a Better Programmer (Day: 3)

Journey, now that was a word I used because it sounded good. these last few days I understanding of that word. I have been on a journey to understand Binary Trees better. these past days I have been traversing through some trees, to learn how they work and I am comfortable enough to walk through a traversing in order Binary tree.

the set up

function Node(val) {
    this.value=val
     this.left=null
     this.right=null
}

var tree2 = new Node(5);
tree2.left = new Node(10);
tree2.left.left = new Node(17);
tree2.left.right = new Node(3);
tree2.right = new Node(8);

Goal: have an array in order of the tree.

How it works
BT(Binary Trees) will always have a root. The root will be where the tree starts just like a real one 🙂. From that root there will be a node that will have two branches, one left and one right, if we are talking about BTS (binary search tree) then the rules for what goes left and right and different(cover this on a different day).

I wanted to make an image with all the numbers I have listed above however, it seems I can't upload a local image.

When you look at the set up you can see the tree is built. Before we start coding, We need to understand how to move in a BT. we start at the furthest “left” record that number then up to the node record that number then to the right and yep, you guessed it, record that node too.

Based on the set up what you do think the sorted array will end up looking like?

1. [5,10,17,3,8]
2. [5,17,10,3,8]
3. [17,5,3,10,8]
4. [17,10,8,5,3]
5. [17,10,3,5,8]
6. [10,17,5,3,8]

let's walk through this, just to make sure we understand what is happening.

so looking at the image of the BT we have “17” being the furthers left (tree2.left.left) then bounce up to the parent node "10" (tree2.left) lastly visit the right node of “10” which is “3” from there we just repeat the exact same process. We go back to node “10” and since we already recorded it we move to the node above “5” and yes we then get the last number “8” which is the furthermost number to the right.

              What tree2 would look like 
                        5
                       / \
                      10  8
                     / \
                    17  3

The Code:

so now that we can do it on paper now let's code it up

function inOrder (tree) {
    let res= [ ]
    helper(tree, res)
    return res
} 

function helper (tree, res) {
  if (tree){
        if (tree.left){
            helper(tree.left, res) //we do this so we keep calling this function 
                                      (recursive) until the node we land on 
                                       doesn’t have a left child.
        }

        res.push(tree.val) // adds the current node to `res` array.

         if (tree.right){  //once the left is done we move tot he right
           helper(tree.right, res)
        }
    }
} 

 inOrder(tree2)

now try this tree:

var tree3 = new Node(6);
tree3.left = new Node(3);

or

var tree1 = new Node(4);
tree1.left = new Node(1);
tree1.right = new Node(3);

and go through the steps and what do you get?

the key for me to understanding this entire process was to talk to the rubber duck. If you aren’t sure what the heck I am talking about check out Rubber Ducky Debugging by @rachelsoderberg.

This has been a struggle for me personally, I understood BT on paper and how it worked but was confusing the rules for BTS, or I was WAY overthinking it, and my code would be 30 lines, with a couple of loops and a few if statements.