Binary Tree Paths

BacktrackingBinary TreeDepth-First SearchTree

Given a binary tree, return all root-to-leaf paths. Each path should be represented as a string formatted as 'root->node1->node2->...->leaf'.

Example 1

Input

[
  [
    1,
    2,
    3,
    null,
    5
  ]
]

Output

["1->2->5", "1->3"]

Explanation. For the given binary tree, there are two root-to-leaf paths: 1 -> 2 -> 5 and 1 -> 3.

Example 2

Input

[
  [
    1
  ]
]

Output

["1"]

Explanation. For a single-node tree, the only root-to-leaf path is the node itself.

Example 3

Input

[
  [
    1,
    2
  ]
]

Output

["1->2"]

Explanation. For this binary tree with only a root and one left child, the root-to-leaf path is 1 -> 2.

Follow-up: Can you implement your solution iteratively?

Constraints:

The binary tree will contain at least one node and at most 100 nodes. Every node in the tree will have a value that is an integer.