CODEWITHSUNDEEP
javascriptalgorithmrecursionbinary-treenodes
Altaf
Altaf

Reputation: 429

Having trouble understanding the recursive portion of a binary tree DFS

I've written this function via trial and error, and I can't seem to understand how the recursive portion is adding the first element or in this case the 1-> in both the paths. Here is the code:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

const binaryTreePaths = root => {
    if (!root) return null
    let results = []
    const dfs = (node, path) => {
        if (!node.left && !node.right) return results.push(path + node.val)
        if (node.left) dfs(node.left, path + node.val + '->')
        if (node.right) dfs(node.right, path + node.val + '->')
    }
    dfs(root, '')
    return results
}

const tree1 = new TreeNode(1)
tree1.left = new TreeNode(2)
tree1.right = new TreeNode(3)
tree1.left.right = new TreeNode(5)

console.log(binaryTreePaths(tree1))

The recursive calls to the left and right nodes add left and right children to the path which I understand, but what in the function adds the first node?

Upvotes: 1

Views: 75

Answers (1)

Bergi
Bergi

Reputation: 664484

It might help to refactor the function a bit:

const dfs = (node, parentPath) => {
    const path = parentPath + node.val;
//                          ^^^^^^^^^^ magic happens here
    if (!node.left && !node.right) return results.push(path)
    if (node.left) dfs(node.left, path + '->')
    if (node.right) dfs(node.right, path + '->')
}

Try stepping through this with a debugger, and log the value of parentPath and path.

Upvotes: 1

Related Questions