educative.io

Educative

Stack approach | Non recursive approach

class TreeNode {

  constructor(value) {

    this.value = value;

    this.left = null;

    this.right = null;

  }

};

const find_sum_of_path_numbers = function(root) {

  let sum = 0

  let que = []

  let path = []

  que.push(root)

  while(que.length){

    let node = que.pop()

    let length = que.length

    path.push(node.value)

    if(node.left !== null) que.push(node.left)

    if(node.right !== null) que.push(node.right)

   

    if(node.right === null && node.left === null) {

      let multiple = path.length - 1

      const reducer = (a, c, i) => {

        const multiple_ = multiple - i

        return c * (10 ** multiple_) + a

      }

      sum += path.reduce(reducer, 0)

    }

    if(que.length > length) {}

    else {

      let count = path.length - que.length

      while(count--) path.pop()

    }

  }  

  return sum

};

const root = new TreeNode(1);

root.left = new TreeNode(0);

root.right = new TreeNode(1);

root.left.left = new TreeNode(1);

root.right.left = new TreeNode(6);

root.right.right = new TreeNode(5);

console.log(`Total Sum of Path Numbers: ${find_sum_of_path_numbers(root)}`);

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Sum of Path Numbers (medium) - Grokking the Coding Interview: Patterns for Coding Questions

Hello @Saad_Khan
Thank you for reaching out to us. We really appreciate learners who think outside of the box and come up with alternate solutions. While the working and output of your code are absolutely correct, it has higher time complexity. Time complexity of your code is: O(n^2) = [O(n) =>while loop* O(n) => .reduce function]. On the other hand, the time complexity of the code provided on the platform is O(n).
I hope this helps!