Javascript Deepest Node

Question

I am having difficulty returning the deepest node of the binary tree. I know how to find the height of the tree but I do not know how to return the deepest node. Below is my code as I try to loop the whole tree and replace the node passed in the argument. However, I only get the root node as a result.

tree.prototype.deepestnode=function()
{
  if(this.root===null)
  {
    return 'none';
  }
  else
  {
    let node=this.root;
    this.root.deepnode(1,1,node);
    return node;
  }
}

node.prototype.deepnode=function(maxdepth,currentdepth,node)
{
  if(maxdepth<currentdepth)
  {
    node=this;
  }
  if(this.left!==null)
  {
    this.left.deepnode(maxdepth,++currentdepth,this.left);
  } 
  if(this.right!==null)
  {   
    currentdepth++;    
    this.right.deepnode(maxdepth,++currentdepth,this.right);
  } 

}


 node.prototype.addnode=function(node)
{
  if(node.value<this.value)
  {
    if(this.left===null)
    {
      this.left=node;
    }
    else
      this.left.addnode(node);
  }
  else if(node.value>this.value)
  {
    if(this.right===null)
    {
      this.right=node;
    }
    else
      this.right.addnode(node);      
  }
}



tree.prototype.addtotree=function(value)
{
  let n=new node(value);
  if(this.root===null)
  {
    this.root=n;
  }
  else
  {
    this.root.addnode(n);
  }
}

Answer 1

Here is my solution to this problem in Javascript in only 6 lines. It returns a tuple with the deepest node and its depth within the tree. I agree with Dimitar that you should look at recursive programming.

The main thing to keep in mind is the base case of the recursive function. In this problem the base case is a leaf of the tree, meaning a node with no children. We cannot go any deeper in the tree from a leaf.

deepest(node = this.getRoot(), level = 0)  {
    // this is the base case, we return the node as it is a leaf
    if (!node.left && !node.right) return {'node' : node, 'level' : level}

    // we continue traversing the tree as we are not at a leaf node 
    // so there must be nodes at a deeper level
    let left = node.left ? this.deepest(node.left, level+1) : { 'level' : -1 }
    let right = node.right ? this.deepest(node.right, level+1) : { 'level' : -1 }

    // return the deeper node
    return (left.level > right.level) ? left : right
}

So depending on how you've implemented your binary tree, one way of calling my deepest function could be:

//you could pass in your root node into the function as a parameter
let obj = deepest() 

console.log('Deepest node: ' + obj.node.value + ', Level: ' + obj.level) 
// e.g 'Deepest node: 12, Level: 4'

Answer 2

You need to spend some time on the recursion (https://en.wikipedia.org/wiki/Recursion_(computer_science). It is a bit tricky sometimes. On the question - here is a working example of it:

    const tree = function () {
    this.root = {};

    this.add = function (root, node) {
        if (!root.value) {
            root.value = node.value;
            return;
        }

        if (root.value > node.value && !root.left) {
            root.left = node;
            return;
        }

        if (root.value <= node.value && !root.right) {
            root.right = node;
            return;
        }

        if (root.value > node.value) {
            this.add(root.left, node);
        } else {
            this.add(root.right, node);
        }
    }

    this.findDeepestNode = function (current, results, currentLevel) {
        if (results.length === 0) {
            results.push({ value: current.value, level: currentLevel })
        }

        if (!current.value) {
            return results;
        }

        if (current) {
            let currentDeepest = results.pop();
            if (currentDeepest.level > currentLevel) {
                results.push(currentDeepest);
            } else {
                results.push({ value: current.value, level: currentLevel });
            }
        }

        if (!current.left && current.right) {
            this.findDeepestNode(current.right, results, ++currentLevel);
        }


        if (!current.right && current.left) {
            this.findDeepestNode(current.left, results, ++currentLevel);
        }

        if (current.left && current.right) {
            this.findDeepestNode(current.left, results, ++currentLevel);
            this.findDeepestNode(current.right, results, currentLevel);
        }

        return results;
    }
};

const node = function (value) {
    this.value = value;
    this.left = {};
    this.right = {};
};

let t = new tree();
t.add(t.root, new node(4));
t.add(t.root, new node(3));
t.add(t.root, new node(2));
t.add(t.root, new node(142));
t.add(t.root, new node(15));
t.add(t.root, new node(26));
t.add(t.root, new node(13));
t.add(t.root, new node(28));

let deepest = t.findDeepestNode(t.root, [], 0);
console.log(deepest);