Skip to content

Commit 6fab6de

Browse files
pradeepkumar24rkpradeepkumar24rk
committed
Add implementations for BinaryTreePath, NQueens, and PathSum classes
1 parent 34f2ed2 commit 6fab6de

File tree

3 files changed

+207
-0
lines changed

3 files changed

+207
-0
lines changed

‎BackTracking/BinaryTreePath.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package BackTracking;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
public class BinaryTreePath {
7+
// TreeNode definition
8+
static class TreeNode {
9+
int val;
10+
TreeNode left, right;
11+
TreeNode(int val) { this.val = val; }
12+
}
13+
14+
public static void main(String[] args) {
15+
// Build sample tree:
16+
// 1
17+
// / \
18+
// 2 3
19+
// \
20+
// 5
21+
TreeNode root = new TreeNode(1);
22+
root.left = new TreeNode(2);
23+
root.right = new TreeNode(3);
24+
root.left.right = new TreeNode(5);
25+
26+
BinaryTreePath sol = new BinaryTreePath();
27+
List<String> paths = sol.binaryTreePaths(root);
28+
29+
System.out.println("Root-to-leaf paths:");
30+
for (String path : paths) {
31+
System.out.println(path);
32+
}
33+
}
34+
35+
public List<String> binaryTreePaths(TreeNode root) {
36+
37+
List<String> sList = new ArrayList<>();
38+
backTrack(root,"",sList);
39+
return sList;
40+
}
41+
42+
static void backTrack(TreeNode root, String str,List<String> sList) {
43+
if(root == null) return;
44+
45+
if(str.length()==0){
46+
str = root.val+"";
47+
} else {
48+
str = str+"->"+root.val+"";
49+
}
50+
51+
if(root.left == null && root.right == null) {
52+
sList.add(str);
53+
return;
54+
}
55+
56+
backTrack(root.left,str,sList);
57+
backTrack(root.right,str,sList);
58+
return;
59+
}
60+
}
61+
62+
// Root-to-leaf paths:
63+
// 1->2->5
64+
// 1->3

‎BackTracking/NQueens.java‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package BackTracking;
2+
3+
public class NQueens {
4+
5+
public static void main(String[] args) {
6+
int n = 4;
7+
boolean[][] board = new boolean[n][n];
8+
int val = solveNQ(board, 0);
9+
System.out.println(val);
10+
}
11+
12+
static void displayBoard(boolean board[][]) {
13+
// for(int[] arr:board) {
14+
// System.out.println(Arrays.toString(arr));
15+
// }
16+
for (boolean[] arr : board) {
17+
for (boolean ele : arr) {
18+
if (ele) {
19+
System.out.print("Q ");
20+
} else {
21+
System.out.print("X ");
22+
}
23+
}
24+
System.out.println();
25+
}
26+
System.out.println();
27+
}
28+
29+
static int solveNQ(boolean[][] board, int row) {
30+
if (row == board.length) {
31+
displayBoard(board);
32+
return 1;
33+
}
34+
35+
int count = 0;
36+
for (int col = 0; col < board[0].length; col++) {
37+
if (isSafe(board, row, col)) {
38+
board[row][col] = true;
39+
count += solveNQ(board, row + 1);
40+
board[row][col] = false;
41+
}
42+
}
43+
return count;
44+
}
45+
46+
static boolean isSafe(boolean[][] board, int row, int col) {
47+
for (int i = 0; i < row; i++) {
48+
if (board[i][col])
49+
return false;
50+
} // top-bottom
51+
52+
// right dia
53+
int rightdia = Math.min(row, (board[0].length - 1) - col);
54+
// System.out.println(rightdia);
55+
for (int i = 1; i <= rightdia; i++) {
56+
if (board[row - i][col + i]) {
57+
return false;
58+
}
59+
}
60+
61+
// left dia
62+
int maxleft = Math.min(row, col);
63+
for (int i = 1; i <= maxleft; i++) {
64+
if (board[row - i][col - i]) {
65+
return false;
66+
}
67+
}
68+
return true;
69+
}
70+
71+
}

‎BackTracking/PathSum.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package BackTracking;
2+
3+
import java.util.*;
4+
5+
public class PathSum {
6+
static class TreeNode {
7+
int val;
8+
TreeNode left, right;
9+
TreeNode(int val) { this.val = val; }
10+
}
11+
12+
public static void main(String[] args) {
13+
// Build sample tree:
14+
// 5
15+
// / \
16+
// 4 8
17+
// / / \
18+
// 11 13 4
19+
// / \ / \
20+
// 7 2 5 1
21+
TreeNode root = new TreeNode(5);
22+
root.left = new TreeNode(4);
23+
root.right = new TreeNode(8);
24+
25+
root.left.left = new TreeNode(11);
26+
root.left.left.left = new TreeNode(7);
27+
root.left.left.right = new TreeNode(2);
28+
29+
root.right.left = new TreeNode(13);
30+
root.right.right = new TreeNode(4);
31+
root.right.right.left = new TreeNode(5);
32+
root.right.right.right = new TreeNode(1);
33+
34+
int targetSum = 22;
35+
36+
PathSum demo = new PathSum();
37+
List<List<Integer>> result = demo.pathSum(root, targetSum);
38+
39+
System.out.println("Paths with sum " + targetSum + ":");
40+
for (List<Integer> path : result) {
41+
System.out.println(path);
42+
}
43+
}
44+
45+
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
46+
List<List<Integer>> pathSum = new ArrayList<>();
47+
backTrack(root, targetSum, 0, new ArrayList<>(), pathSum);
48+
return pathSum;
49+
}
50+
51+
static void backTrack(TreeNode root, int targetSum, int sum, List<Integer> path, List<List<Integer>> pathSum) {
52+
if (root == null) return;
53+
54+
sum += root.val;
55+
path.add(root.val);
56+
57+
backTrack(root.left, targetSum, sum, path, pathSum);
58+
backTrack(root.right, targetSum, sum, path, pathSum);
59+
60+
if (root.left == null && root.right == null && sum == targetSum) {
61+
pathSum.add(new ArrayList<>(path));
62+
}
63+
64+
path.remove(path.size() - 1);
65+
}
66+
}
67+
68+
// Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
69+
// Output: [[5,4,11,2],[5,8,4,5]]
70+
// Explanation: There are two paths whose sum equals targetSum:
71+
// 5 + 4 + 11 + 2 = 22
72+
// 5 + 8 + 4 + 5 = 22

0 commit comments

Comments
 (0)