# All the paths from the root to the leaves

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))

• I could've sworn there was an answer on this question... – Mast Aug 27 '18 at 17:52
• 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. – Mast Aug 27 '18 at 17:52
• I've put your question back in the state it was, but keep the above in mind should you receive an answer. – Mast Aug 27 '18 at 17:56
• @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? – Rick Aug 27 '18 at 18:33
• Your test cases should be included from the start. – Mast Aug 27 '18 at 18:38