I am practicing InterviewBit challenge Path to Given Node, but I keep having problems:
First if I keep my helper function (traverse) in the structure like this, when I run the code it says traverse is not defined.
I tried moving the function inside solve(A, B) but then it says I don't get the correct result. My code is at the bottom.
The question is simple: find the path to the node B in binary tree A.
Problem Description:
Given a Binary Tree A containing N nodes.
You need to find the path from Root to a given node B.
NOTE:
No two nodes in the tree have same data values. You can assume that B is present in the tree A and a path always exists.
Example Input
Input 1:
A =
1 / \ 2 3 / \ / \ 4 5 6 7B = 5
Input 2:
A =
1 / \ 2 3 / \ \ 4 5 6B = 1
Example Output
Output 1:
[1, 2, 5]
Output 2:
[1]
// Definition for a binary tree node // function TreeNode(data){ // this.data = data // this.left = null // this.right = null // }
module.exports = {
//param A : root node of tree
//param B : integer
//return a array of integers
solve : function(A, B){
// traverse tree
// each traversal append a new node
// if the leaf is not the node, return earlier traversal
// like if from left to right we find nothing at all, we return earlier traversal
path = traverse(A, B, []);
return path;
},
traverse: function(node, target, traversal) {
if (node) {
traversal.push(node.data);
if (node.data === target) return traversal;
traversal = traverse(node.left, target, traversal);
traversal = traverse(node.right, target, traversal);
traversal.pop();
}
return traversal;
},
};
When you define traverse as a property of the exported object, you need to call it as this.traverse(). But it seems better to do the alternative and define it as a local function in the scope of solve.
The problem that you then bump into is that even when you find a path, you still .pop() elements from it, so that will not work.
When coming back from a recursive call that found the path, you should not search any further and immediately return that same path to the caller, who will do the same, ... until the original caller gets that path.
Another thing you should avoid: don't define path as a global variable. Declare it explicitly with const, let or var.
So change as follows:
solve : function(A, B){
function traverse(node, target, traversal) {
if (node) {
traversal.push(node.data);
if (node.data === target) return traversal;
let success = traverse(node.left, target, traversal);
if (success) return success;
success = traverse(node.right, target, traversal);
if (success) return success;
traversal.pop();
}
}
// Declare!
let path = traverse(A, B, []);
return path;
This will fix it.
Now think how you can do better, and avoid passing along a third argument. You can use the solve function recursively and build the correct path when backtracking out of recursion.