Binary Tree Paths
Fri May 10 2024 Recursive Depth-First Search (DFS):
Employing a recursive approach, we traverse the binary tree to explore all possible paths.
Path Construction:
As we traverse the tree, we construct paths from the root to each leaf node, appending node values along the way.
Leaf Node Detection:
When reaching a leaf node (a node with no children), we add the constructed path to our list of paths.
Backtracking:
After exploring a path, we backtrack to explore other possible paths, ensuring all paths are thoroughly examined.
1//https://leetcode.com/problems/binary-tree-paths/description/
2
3class Node {
4 constructor(val) {
5 this.val = val;
6 this.left = null;
7 this.right = null;
8 }
9 }
10
11
12 const one = new Node(1);
13 const two = new Node(2);
14 const three = new Node(3);
15 const threeRight = new Node(3);
16 const twoRight = new Node(2);
17 const four = new Node(4);
18 const fourRight = new Node(4);
19 const five = new Node(5);
20 const six = new Node(6);
21 const seven = new Node(7);
22 const eight = new Node(8);
23
24
25 one.left = two;
26 one.right = three;
27 two.right = five;
28 two.left = four;
29 five.right = seven;
30 five.left = six;
31 seven.left = eight;
32
33 var binaryTreePaths = function(root) {
34
35 let paths = [];
36 function dfs(node, currentPath) {
37 if (!node) {
38 return;
39 }
40if(currentPath.length > 0){
41 currentPath += '->' + node.val;
42 }else{
43 currentPath = node.val.toString();
44 }
45
46
47 if(!node.left && !node.right){
48 paths.push(currentPath)
49 }else{
50 dfs(node.left, currentPath);
51 dfs(node.right, currentPath);
52 }
53 }
54 dfs(root, '');
55 return paths;
56};
57
58console.log(binaryTreePaths(one))
59