improve readability of code.

Source Link

edited Aug 23, 2018 at 23:32

Rick

586
5
16

function diameterOfBinaryTree(root) {
  let stack = [
    [1, root]
  ];
  let d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let tuple[indicator, node] = [...stack.pop(),
      indicator = tuple[0],
      node = tuple[1];];
    if (indicator) {
      let place = 0,
        extend = [];
      extend[place++] = [0, node]
      if (node.right !== null) {
        extend[place++] = [1, node.right]
      }
      if (node.left !== null) {
        extend[place++] = [1, node.left]
      }
      stack.push.apply(stack, extend);
    } else {
      let left = d.get(node.left) + 1 || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

function diameterOfBinaryTree(root) {
  let stack = [
    [1, root]
  ];
  let d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let tuple = stack.pop(),
      indicator = tuple[0],
      node = tuple[1];
    if (indicator) {
      let place = 0,extend = [];
      extend[place++] = [0, node]
      if (node.right !== null) {
        extend[place++] = [1, node.right]
      }
      if (node.left !== null) {
        extend[place++] = [1, node.left]
      }
      stack.push.apply(stack, extend);
    } else {
      let left = d.get(node.left) + 1 || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

function diameterOfBinaryTree(root) {
  let stack = [
    [1, root]
  ];
  let d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let [indicator, node] = [...stack.pop()];
    if (indicator) {
      let place = 0,
        extend = [];
      extend[place++] = [0, node]
      if (node.right !== null) {
        extend[place++] = [1, node.right]
      }
      if (node.left !== null) {
        extend[place++] = [1, node.left]
      }
      stack.push.apply(stack, extend);
    } else {
      let left = d.get(node.left) + 1 || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

deleted 26 characters in body

Source Link

edited Aug 23, 2018 at 23:09

Rick

586
5
16

Iterative approach: takes 85 steps. However, the number of steps will double as the tree gets larger compared to the recursive functionbranches become more nested. That's because as Iyou walk the nodes, I walk themthey are walked in trios counting. Counting the root nodes branchesroots while unpacking the right and left nodes, culminatingside. Culminating the countcounts on every retrograde iteration as I passunpacking, while passing every root object more than once. time complexity is O(N^2) for every nested object added it will be touched twice, once on entering and a second time on exiting.

make more readable

Source Link

edited Aug 23, 2018 at 23:00

Rick

586
5
16

Iteratively determine the diameter/(god number) of a (directed) binary tree (without recursion)

Iterative approach: takes 85 steps. However, the number of steps will double as the tree gets larger compared to the recursive function. That's because as I walk the nodes, I walk them in trios counting the root nodes branches while unpacking the right and left nodes, culminating the count on every retrograde iteration as I pass every root object more than once. time complexity is O(N^2) for every nested object added it will be touched twice, once on entering and a second time on exiting.

function diameterOfBinaryTree( root) {
  let stack = [[1[
    [1, root]];root]
  ];
  let d=d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let mtuple = stack.pop(), indicator = m[0], node = m[1];
    if ( indicator) {
= tuple[0],
     if (node.right === null && node.left === null)= {tuple[1];
       if stack.push([0, node]indicator)
        continue
      }{
      let countplace = 0;
      let 0,extend = [];
      extend[count++]extend[place++] = [0, node]
      if (node.right !== null && node.left !== null) {
        extend[count++]extend[place++] = [1, node.right]
        extend[count++] = [1, node.left]
        stack.push.apply(stack, extend); 
        continue
      }
      if (node.rightleft !== null) {
        extend[count++]extend[place++] = [1, node.right]
        stack.push.apply(stack, extend);
        continue;left]
      } 
      if (node.left !== null) {
        extend[count++] = [1, node.left]
        stack.push.apply(stack, extend);
        continue;
      }
    } else {
      let left = d.get(node.left) + 1  || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;  
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

Iteratively determine the diameter/(god number) of a (directed) binary tree (without recursion)

Iterative approach: takes 85 steps. However, the number of steps will double as the tree gets larger compared to the recursive function. That's because as I walk the nodes I walk them in trios counting the root nodes branches while unpacking the right and left nodes, culminating the count on every retrograde iteration as I pass every root object more than once. time complexity is O(N^2) for every nested object added it will be touched twice, once on entering and a second time on exiting.

function diameterOfBinaryTree( root) {
  let stack = [[1, root]];
  let d= new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let m = stack.pop(), indicator = m[0], node = m[1];
    if (indicator) {
      if (node.right === null && node.left === null) {
        stack.push([0, node])
        continue
      }
      let count = 0;
      let extend = [];
      extend[count++] = [0, node]
      if (node.right !== null && node.left !== null) {
        extend[count++] = [1, node.right]
        extend[count++] = [1, node.left]
        stack.push.apply(stack, extend); 
        continue
      }
      if (node.right !== null) {
        extend[count++] = [1, node.right]
        stack.push.apply(stack, extend);
        continue;
      } 
      if (node.left !== null) {
        extend[count++] = [1, node.left]
        stack.push.apply(stack, extend);
        continue;
      }
    } else {
      let left = d.get(node.left) + 1  || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node,Math.max(left,right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;  
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

Iteratively determine the diameter of a binary tree

Iterative approach: takes 85 steps. However, the number of steps will double as the tree gets larger compared to the recursive function. That's because as I walk the nodes, I walk them in trios counting the root nodes branches while unpacking the right and left nodes, culminating the count on every retrograde iteration as I pass every root object more than once. time complexity is O(N^2) for every nested object added it will be touched twice, once on entering and a second time on exiting.

function diameterOfBinaryTree(root) {
  let stack = [
    [1, root]
  ];
  let d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let tuple = stack.pop(),
      indicator = tuple[0],
      node = tuple[1];
    if (indicator) {
      let place = 0,extend = [];
      extend[place++] = [0, node]
      if (node.right !== null) {
        extend[place++] = [1, node.right]
      }
      if (node.left !== null) {
        extend[place++] = [1, node.left]
      }
      stack.push.apply(stack, extend);
    } else {
      let left = d.get(node.left) + 1 || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

updated title

Link

edited Aug 23, 2018 at 22:16

Rick

586
5
16

Loading

edited tags

Source Link

edited Aug 23, 2018 at 22:00

Rick

586
5
16

Loading

edited tags

Link

edited Aug 23, 2018 at 21:48

Rick

586
5
16

Loading

added 226 characters in body

Source Link

edited Aug 23, 2018 at 21:24

Rick

586
5
16

Loading

added 85 characters in body

Source Link

edited Aug 23, 2018 at 19:45

Rick

586
5
16

Loading

added early exit's

Source Link

edited Aug 23, 2018 at 19:28

Rick

586
5
16

Loading

removed unnecessary set

Source Link

edited Aug 23, 2018 at 17:48

Rick

586
5
16

Loading

removed unnecessary continue

Source Link

edited Aug 23, 2018 at 17:43

Rick

586
5
16

Loading

added base line recursive function, and updated iterative approach

Source Link

edited Aug 23, 2018 at 17:31

Rick

586
5
16

Loading

edited tags

Link

edited Aug 22, 2018 at 4:35

Rick

586
5
16

Loading

Source Link

asked Aug 22, 2018 at 0:31

Rick

586
5
16

Loading

Stack Exchange Network

Return to Question

Iteratively determine the diameter/(god number) of a (directed) binary tree (without recursion)

Iteratively determine the diameter/(god number) of a (directed) binary tree (without recursion)

Iteratively determine the diameter of a binary tree