Diameter of Binary Tree

Description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution(javascript)

// 1: recursion
// const diameterOfBinaryTree = (root) => {
//   let max = 0
//   const aux = (node = root) => {
//     if (!node) {
//       return -1
//     }

//     const leftHeight = aux(node.left) + 1
//     const rightHeight = aux(node.right) + 1
//     max = Math.max(max, leftHeight + rightHeight)
//     return Math.max(leftHeight, rightHeight)
//   }
//   aux(root)
//   return max
// }


// 2: Iteration
const diameterOfBinaryTree = (root) => {
  let max = 0
  if (!root) {
    return max
  }
  const stack = [root]
  const map = new Map()
  while (stack.length) {
    const node = stack[stack.length - 1]

    if (node.left && !map.has(node.left)) {
      stack.push(node.left)
    } else if (node.right && !map.has(node.right)) {
      stack.push(node.right)
    } else {
      const left = map.get(node.left) || 0
      const right = map.get(node.right) || 0
      map.set(node, 1 + Math.max(left, right))
      max = Math.max(max, left + right)
      stack.pop()
    }
  }
  return max
}