CODEWITHSUNDEEP
javascriptalgorithmtreetraversal
davidatthepark
davidatthepark

Reputation: 1365

Return path from root to node in a binary tree

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"

Upvotes: 0

Views: 520

Answers (3)

Varun Hegde
Varun Hegde

Reputation: 349

const findPathFromRoot = (root, target, path = "") => {
  if (root === null) {
    return null;
  }
  path = path + root.val;
  if (root === target) {
    return path;
  }

  const left = findPathFromRoot(root.left, target, path);
  const right = findPathFromRoot(root.right, target, path);

  return left || right;
};

Why does this work?

Return statement always returns to the caller, in your case you are returning only when you find the target is found which in turn returns back to one of findPathFromRoot(currentNode.left, ...) or findPathFromRoot(currentNode.right, ...). But these don't return themselves. So the fix to your code is to return if you find the target either in your left or the right subtree.

Upvotes: 2

kf7ags
kf7ags

Reputation: 268

You need to put in logic to decide whether to travel left or right from the current node's value and call your method with with the currentNode.left or currentNode.right depending on that logic. Then return either when you get a null value (that means the target doesn't exist in the tree) or return when the currentNode.value === target.

There's also a problem with your tree though, all values to the left of your root need to be larger than the root's value, and all values on the right of the root need to be smaller, but it looks like the 2 is on the left of the root (who's value is 3).

Upvotes: 0

Keith
Keith

Reputation: 24191

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"

Upvotes: 1

Related Questions