CODEWITHSUNDEEP
javascriptnode.jsbinary-tree
LeT
LeT

Reputation: 37

Recursion in right subtree

I am trying to do different problems each day in order to become more flexible writing code, yet this one stopped me in my tracks so far.

The following code is supposed to build up a binary tree from a given String in preOrder traversal. I.e., "5 3 1 N N N 7 N N" for the following binary tree. Elements are separated by spaces, N marks empty nodes, which are just null. 

             5
            / \
          3     7
         /
        1

It should be as simple as walking through the split up string and when something other than "N" is found, a Node is constructed with the value, and the Index increased.

After the index was increased, I recur to put the next array element into the left subtree. If "N" is encountered, nothing needs to be done because a node's constructor already has the left child set as null, so I only increase the index. Theoretically, the right node should be assigned in the previous recursion step... yet somehow that fails?

Is it because of JavaScript's async behaviour? What did I miss?

Thank you in advance for your help! 

class Node {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

class Index {
    constructor() {
        this.index = 0;
    }
    incr() {
        this.index++;
    }
}

function deserialize(treeString) {
    let treeArray = treeString.split(" ");
    let index = new Index();
    let length = treeArray.length;
    function helper(index) {
        if (index.index < length) {
            let node = null;
            if (treeArray[index.index] !== "N") {
                node = new Node(parseInt(treeArray[index.index], 10));
                index.incr();
                node.left = helper(index);
                node.right = helper(index);
            } else {
                index.incr();
            } 
            return node;
        };
    }
    return helper(index);
}

Upvotes: 0

Views: 365

Answers (1)

grodzi
grodzi

Reputation: 5703

I don't get your error because console.log(JSON.stringify(deserialize('5 3 1 N N N 7 N N'),null,1)) does give me

{
    "val": 5,
    "right": {
        "val": 7,
        "right": null,
        "left": null
    },
    "left": {
        "val": 3,
        "right": null,
        "left": {
            "val": 1,
            "right": null,
            "left": null
        }
    }
}

which seems to be your intended result

we can do a bit "simpler though"

  1. prevent yourself from useless indentation

Especially for stops on recursive condition, it is best practice to write them first

function recurse(){
    if (index.index == length) {
        //stop code
        return 
    }
    //your other conditions...
    //your code which will call recurse
}

2.1 your "iterator" here is useless

since you are still dependant to know your structure (treeArray must "implement" operator[]), taking a dumb variable will at least be less code

2.2 if you really want to use an iterator

you see that whether in your if or else path, you incr (which is equivalent to "advance in treeArray"). So just iterate over treeArray. Below we "pop" elements (forwardly")

function helper(arr){
    if end
        return
    let currentNodeVal = arr.shift() //advance in treeArray
    if (currentNodeVal !== "N") {
        node = new Node(parseInt(currentNodeVal, 10));
        node.left = helper(arr);
        node.right = helper(arr);
    } else {
        //nothing to do
    } 
}
  1. Is it because of JavaScripts async behaviour?

Here you actually don't have any asynchronous code running. If you named

helperinfty = function(){
    while(true){}
}
node.left = helperinfty(arr)
node.right = helper(arr);

you could observe that node.right = helper(arr) is never executed. You get the "funky" stuff when you use setTimeout, etc (put it simply when a function needs a callback to sync flow) (answer is no)

  1. simplified code

prints the same tree as in beginning

class Node {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

function deserialize(treeString) {
    let arr = treeString.split(" ");
    function helper(arr) {
        if(arr.length == 0)return null;//note that in previous implem helper "could" return undefined...which is not something desired
        let current = arr.shift();
        if (current == "N"){
            //this is a matter of preference. Arguably one can prefer your style.
            //I prefer to emphase that when N is found it is meant to be a null node, and "abort" any recursion
            return null
        }
        let node = new Node(parseInt(current, 10));
        node.left = helper(arr);
        node.right = helper(arr);
        return node;
    }
    return helper(arr);
}
x = deserialize('5 3 1 N N N 7 N N');
console.log(JSON.stringify(x, null, 4))

Upvotes: 3

Related Questions