Return path from root to node in a binary tree

Question

I'm trying to accomplish something that seems simple but having trouble implementing it. Given a binary tree and a node, return the path. I attempted it below but I am really stuck. I am also not entirely sure how to exit out of the recursive function once I find the target node.

const tree = {
  val: 3,
  left: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 2,
      left: null,
      right: null
    }
  },
  right: {
    val: 1,
    left: null,
    right: null
  }
};

const findPathFromRoot = (currentNode, targetNode, path) => {
  path + currentNode.val;

  if (currentNode === targetNode) {
    return path + targetNode.val;
  }

  findPathFromRoot(currentNode.left, targetNode, path);
  findPathFromRoot(currentNode.right, targetNode, path);
}

const target = tree.left.right;
console.log(findPathFromRoot(tree, target, '')); // should return "352"

Answer 1

Like mentioned in comments, if your tree was sorted this could be made faster.

As is, every node needs to be checked..

You was nearly there with what you attempted, first you need to check if you have a left or right node, then I check the left node, if this finds the node down this tree is will return, if it does not it will then try the right node. It does this recursively so that every possible node is visited.

Below is a working example..

const tree = {
  val: 3,
  left: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 2,
      left: null,
      right: null
    }
  },
  right: {
    val: 1,
    left: null,
    right: null
  }
};

const findPathFromRoot = (currentNode, targetNode, path) => {
  path += currentNode.val;
  if (currentNode === targetNode) {
    return path;
  }
  let ret = null;
  if (currentNode.left) ret = findPathFromRoot(currentNode.left, targetNode, path);
  if (currentNode.right && !ret) ret = findPathFromRoot(currentNode.right, targetNode, path);
  return ret;
}

const target = tree.left.right;
console.log(findPathFromRoot(tree, target, '')); // should return "352"