CODEWITHSUNDEEP
javascriptbinary-tree
Thomas T
Thomas T

Reputation: 83

Get path to a node in a binary tree recursively

The path I'm getting is wrong - the recursion doesn't stop on the end condition. I have a tree node defined like this:

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

A tree:

enter image description here

And a function:

const getPath = function(root, node) {
    let path = [];

    const traverse = function(root, node) {
        if (root.left || root.right) {
            path.push(root.val);
        }
        if (root.val === node.val) {
            path.push(root.val);
            return;
        }
        if (root.left) {
            traverse(root.left, node);
        }
        if (root.right) {
            traverse(root.right, node);
        }
    };
    traverse(root, node);
    return path;
};

If I want to get the path to element 7, the output would be [3, 5, 2, 7] because that's the path from the root to that node.

But the output of my function is [3, 5, 2, 7, 1] instead - it seems like it doesn't stop on the return condition but keeps going with whatever it has on a stack.

What's wrong with this code?

Example for the tree from my image:

const T = new TreeNode(3);
T.left = new TreeNode(5);
T.right = new TreeNode(1);
T.left.left = new TreeNode(6);
T.left.right = new TreeNode(2);
T.left.right.left = new TreeNode(7);
T.left.right.right = new TreeNode(4);
T.right.left = new TreeNode(0);
T.right.right = new TreeNode(8);


const node = T.left.right.left;
const path = getPath(T, node); // [3, 5, 2, 7, 1]

Upvotes: 0

Views: 1370

Answers (2)

slider
slider

Reputation: 12990

You can keep track of whether or not you've found your node in another variable while doing a usual pre-order traversal. Based on whether or not you've found the node, you can append the current value to path, or pop if it wasn't found in any of the subtrees:

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

const getPath = function(root, node) {
  let path = [];
  let found = false;

  const traverse = function(curr) {
    if (!curr || found) return;
    if (curr.val == node.val) found = true;
    
    path.push(curr.val);
    traverse(curr.left);
    traverse(curr.right);
    if (!found) path.pop();
  };

  traverse(root, node);
  return path;
};

const T = new TreeNode(3);
T.left = new TreeNode(5);
T.right = new TreeNode(1);
T.left.left = new TreeNode(6);
T.left.right = new TreeNode(2);
T.left.right.left = new TreeNode(7);
T.left.right.right = new TreeNode(4);
T.right.left = new TreeNode(0);
T.right.right = new TreeNode(8);

console.log(getPath(T, T.left.right.left));
console.log(getPath(T, T.right.left));
console.log(getPath(T, T.left.left));

Upvotes: 0

CertainPerformance
CertainPerformance

Reputation: 371138

You should only push if the the left or right finds a match. (Right now, you're pushing unconditionally in the first if.) One possibility is to create the array to return only when a match is found (that is, after recursion has found the match, and you're bubbling back up the tree and call stack):

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
const getPath = function(root, valToFind) {
    if (root.val === valToFind) {
        // found: create the array to return
        return [root.val];
    }
    if (root.left) {
        const result = getPath(root.left, valToFind);
        if (result) {
            // unshift: add this node's value to the beginning of the array
            result.unshift(root.val);
            return result;
        }
    }
    if (root.right) {
        const result = getPath(root.right, valToFind);
        if (result) {
            result.unshift(root.val);
            return result;
        }
    }
};

const T = new TreeNode(3);
T.left = new TreeNode(5);
T.right = new TreeNode(1);
T.left.left = new TreeNode(6);
T.left.right = new TreeNode(2);
T.left.right.left = new TreeNode(7);
T.left.right.right = new TreeNode(4);
T.right.left = new TreeNode(0);
T.right.right = new TreeNode(8);


const node = T.left.right.left;
console.log(getPath(T, node.val)); // [3, 5, 2, 7]
console.log(getPath(T, 4));
console.log(getPath(T, 8));
console.log(getPath(T, 6));

Upvotes: 2

Related Questions