3
\$\begingroup\$

Given a binary tree, return all root-to-leaf paths.

Example:

-- 1
 /   \
2     3
 \
  5

Output should be: ["1->2->5", "1->3"]

My approach: I walk the branches from left to right, finding the first leaf on the leftward tangent collecting the segments until the last node. I collect the vectors of the tree into a passing stack. On exhausting every leftward vector I stop collecting the segments. I look to the right vector and see if a pathway exists. I turn on segment collection and reorient on a parallel trajectory adjacent to the right vector.

On reaching the last node I push a copy of the current state of the passing stack to the list of paths. I traverse back up the frames removing the collected paths by popping() them from the passing stack, and my current position.

As I slingshot back up the frames, to the beginning. I exploring the right vectors and I stack the frames and branch down the path on every opening. I collect the nodes values into the passed stack on entering and push a copy of the current state of the passed stack on reaching every leaf. On exiting the branching frames, I removing from the passed stack every value as I travel back to the beginning, branching on every fork along the frames.

Time complexity is \$O(n^2)\$ where \$n\$ is the number of nodes. I touch both the right and left vectors of the recursion. The left on entering and right on exiting.

function binaryTreePaths(root) {
  const paths = [];
  let moveLeft = true;

  function pathsInternal(node, stack = []) {
    if (moveLeft) stack.push(node.val)
    if (node.left) pathsInternal(node.left, stack)
    else moveLeft = false;
    if (node.right) {
      moveLeft = true
      pathsInternal(node.right, stack)
    } else {
      if (node.left === null) paths.push(stack.slice())
    }
    stack.pop()
    return paths
  }
  return pathsInternal(root).map(x => x.join("->"))
}

const leaves1 = {
  "val": 1,
  "right": {
    "val": 3,
    "right": null,
    "left": null
  },
  "left": {
    "val": 2,
    "right": {
      "val": 5,
      "right": null,
      "left": null
    },
    "left": null
  }
}
leaves2 = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 3,
      left: {
        val: 4,
        left: {
          val: 5,
          left: null,
          right: null
        },
        right: null
      },
      right: {
        val: 6,
        left: null,
        right: null
      }
    },
    right: {
      val: 7,
      left: {
        val: 8,
        left: {
          val: 9,
          left: null,
          right: null
        },
        right: null
      },
      right: {
        val: 10,
        left: {
          val: 11,
          left: {
            val: 12,
            left: {
              val: 13,
              left: null,
              right: null
            },
            right: null
          },
          right: {
            val: 14,
            left: null,
            right: null
          }
        },
        right: {
          val: 15,
          left: {
            val: 16,
            left: null,
            right: {
              val: 17,
              left: {
                val: 18,
                left: null,
                right: null
              },
              right: null
            }
          },
          right: null
        }
      }
    }
  },
  right: {
    val: 19,
    left: null,
    right: {
      val: 20,
      left: null,
      right: {
        val: 21,
        left: {
          val: 22,
          left: {
            val: 23,
            left: null,
            right: null
          },
          right: null
        },
        right: {
          val: 24,
          left: {
            val: 25,
            left: {
              val: 26,
              left: {
                val: 27,
                left: null,
                right: null
              },
              right: null
            },
            right: {
              val: 28,
              left: null,
              right: null
            }
          },
          right: null
        }
      }
    }
  }
};


console.log(binaryTreePaths(leaves1))
console.log(binaryTreePaths(leaves2))

Second approach: In my second approach I only touch every element once. I believe this makes it linear but I am not positive?

function branchPaths(tree) {
  const paths = [],
    rightIndexes = new WeakMap(),
    map = new Map();

  function leaves(root, cpaths = []) {
    let stack = [];
    while (root) {
      let index = cpaths.push(root.val)
      if (root.right) {
        stack.push(root.right)
        rightIndexes.set(root.right, index - 1)
      }
      map.set(root.val, root)
      root = root.left
    }
    let pier = map.get(cpaths[cpaths.length - 1])
    if (!pier.right && !pier.left) paths.push(cpaths)
    while (stack.length) {
      let right = stack.pop(),
        origin = rightIndexes.get(right),
        slice = cpaths.slice(0, origin + 1);
      leaves(right, slice)
    }
    return paths.map(x => x.join('->'))
  }
  return leaves(tree)
}
const tree1 = {
  "val": 1,
  "right": {
    "val": 3,
    "right": {
      "val": 4,
      "right": null,
      "left": null
    },
    "left": null
  },
  "left": {
    "val": 2,
    "right": {
      "val": 5,
      "right": null,
      "left": null
    },
    "left": null
  }
}

const tree2 = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 3,
      left: {
        val: 4,
        left: {
          val: 5,
          left: null,
          right: null
        },
        right: null
      },
      right: {
        val: 6,
        left: null,
        right: null
      }
    },
    right: {
      val: 7,
      left: {
        val: 8,
        left: {
          val: 9,
          left: null,
          right: null
        },
        right: null
      },
      right: {
        val: 10,
        left: {
          val: 11,
          left: {
            val: 12,
            left: {
              val: 13,
              left: null,
              right: null
            },
            right: null
          },
          right: {
            val: 14,
            left: null,
            right: null
          }
        },
        right: {
          val: 15,
          left: {
            val: 16,
            left: null,
            right: {
              val: 17,
              left: {
                val: 18,
                left: null,
                right: null
              },
              right: null
            }
          },
          right: null
        }
      }
    }
  },
  right: {
    val: 19,
    left: null,
    right: {
      val: 20,
      left: null,
      right: {
        val: 21,
        left: {
          val: 22,
          left: {
            val: 23,
            left: null,
            right: null
          },
          right: null
        },
        right: {
          val: 24,
          left: {
            val: 25,
            left: {
              val: 26,
              left: {
                val: 27,
                left: null,
                right: null
              },
              right: null
            },
            right: {
              val: 28,
              left: null,
              right: null
            }
          },
          right: null
        }
      }
    }
  }
};


console.log(branchPaths(tree1))
console.log(branchPaths(tree2))

\$\endgroup\$
  • \$\begingroup\$ I could've sworn there was an answer on this question... \$\endgroup\$ – Mast Aug 27 '18 at 17:52
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Aug 27 '18 at 17:52
  • \$\begingroup\$ I've put your question back in the state it was, but keep the above in mind should you receive an answer. \$\endgroup\$ – Mast Aug 27 '18 at 17:56
  • \$\begingroup\$ @Mast but his answer is wrong. He asked for an additional test case showing how he was wrong. Am I not suppose to added test cases showing how the user was wrong when they ask for the test case? \$\endgroup\$ – Rick Aug 27 '18 at 18:33
  • 1
    \$\begingroup\$ Your test cases should be included from the start. \$\endgroup\$ – Mast Aug 27 '18 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.