JavaScript Program to Print Root to Node Path in a Binary Tree
Given a binary tree and a target Node value, we have to find the path from the root of the tree to the node containing the given value.
Example:
Input: binary tree
1
/ \
2 3
/ \
4 5
Target node: 4
Output:
path: 1->2->4
Below are the approaches to print Root to Node Path in a Binary Tree:
Table of Content
- Recursive approach
- Iterative approach
Recursive approach
In this approach we define a recursive function to find the path from the root to a target node in the binary tree. first function checks if the root is null, if it is then function returns null indicating that the target node was not found in this subtree. Then function recursively explores the left and right subtrees and pushes the current node’s value to the path array. When the target node is found it prints the path. If the target node is not found in either subtree, the function backtracks by removing the last element from the path array.
Example: To demonstrate printing Root to Node Path in a Binary Tree using recursive approach.
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
function printPath(root, target, path = []) {
if (root === null) return null;
path.push(root.val);
if (root.val === target) {
console.log(path.join(' -> '));
return path;
}
if (
(root.left !== null && printPath(root.left, target, path)) ||
(root.right !== null && printPath(root.right, target, path))
) {
return path;
}
path.pop();
return null;
}
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(7);
root.right.right.left = new Node(8);
const value = 7;
const path = printPath(root, value);
Output
1 -> 3 -> 7
Time Complexity: O(n)
Space Complexity: O(n)
Iterative approach
The iterative approach uses a stack to perform a depth-first search iteratively. We initialize a stack to keep track of nodes to visit. we use a while loop explore the tree iteratively. In each iteration we pop a node from the stack and its value is checked against the target value. If the current node’s value matches the target value then we print the path. If the target node is not found then we push child nodes to the stack along with an updated path array that includes the child node’s value. This process continues until the stack is empty until stack becomes empty to ensure we visited every node.
Example: To demonstrate printing root to node path in a binary tree using iterative approach.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function printPath(root, target) {
if (!root) return null;
const stack = [{ node: root, path: [root.value] }];
while (stack.length > 0) {
const { node, path } = stack.pop();
if (node.value === target) {
console.log(path.join(" -> "));
return;
}
if (node.right) {
stack
.push({ node: node.right, path: path.concat(node.right.value) });
}
if (node.left) {
stack
.push({ node: node.left, path: path.concat(node.left.value) });
}
}
}
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
const targetNode = 6;
printPath(root, targetNode);
Output
1 -> 3 -> 6
Time Complexity: O(n)
Space Complexity: O(n)