Skip to content

Commit efe8cdd

Browse files
amangit1314amangit1314
committed
#Modification 76
1 parent ed9dd50 commit efe8cdd

15 files changed

Lines changed: 395 additions & 14 deletions

‎.vscode/settings.json‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
{
2+
"java.project.sourcePaths": [
3+
"bst"
4+
]
5+
}

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11

2-
# Java Placement Prepration DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[156/450]
2+
# Java Placement Prepration DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[159/450]
33
🐼 This is a full fledged repository for learning Java Language & DSA for Placement Prepration.
44

55
💪 Here you can find the solution's of **_450 Questions of (Data Structure & Algorithms Cracker Sheet)_** By **LOVE BABBAR** Bhaiya.

binarySearchTree/Find_a_value_in_bst.java renamed to bst/Problem_1.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
1-
package binarySearchTree;
21

3-
public class Find_a_value_in_bst {
2+
3+
public class Problem_1 {
44

55
class Node {
66
int key;
@@ -15,7 +15,7 @@ public Node(int item) {
1515
Node root;
1616

1717
// ! Constructor
18-
Find_a_value_in_bst() {
18+
Problem_1() {
1919
root = null;
2020
}
2121

@@ -52,7 +52,7 @@ void inorderRec(Node root) {
5252
}
5353

5454
public static void main(String[] args) {
55-
Find_a_value_in_bst tree = new Find_a_value_in_bst();
55+
Problem_1 tree = new Problem_1();
5656
tree.insert(50);
5757
tree.insert(30);
5858
tree.insert(20);

binarySearchTree/Deletion_of_a_node_in_bst.java renamed to bst/Problem_2.java

Lines changed: 5 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,7 @@
1-
package binarySearchTree;
21

3-
/**
4-
* Deletion_of_a_node_in_bst
5-
*/
6-
public class Deletion_of_a_node_in_bst {
2+
3+
// Problem Title => Deletion_of_a_node_in_bst
4+
public class Problem_2 {
75
class Node {
86
int key;
97
Node left, right;
@@ -16,7 +14,7 @@ class Node {
1614

1715
Node root;
1816

19-
Deletion_of_a_node_in_bst() {
17+
Problem_2() {
2018
root = null;
2119
}
2220

@@ -81,7 +79,7 @@ void inorderRec(Node root) {
8179
}
8280

8381
public static void main(String[] args) {
84-
Deletion_of_a_node_in_bst tree = new Deletion_of_a_node_in_bst();
82+
Problem_2 tree = new Problem_2();
8583
// * Let us create following BST
8684
// ? 50
8785
// ? / \

‎bst/Problem_3.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
// Problem Tiitle => Find min and max value in a BST
2+
3+
public class Problem_3 {
4+
5+
static class Node {
6+
int data;
7+
Node left, right;
8+
9+
Node(int d) {
10+
data = d;
11+
left = right = null;
12+
}
13+
}
14+
15+
static Node head;
16+
17+
Node insert(Node node, int data) {
18+
if (node == null)
19+
return (new Node(data));
20+
21+
else {
22+
if (data <= node.data)
23+
node.left = insert(node.left, data);
24+
else
25+
node.right = insert(node.right, data);
26+
27+
return node;
28+
}
29+
}
30+
31+
// Returns the min value in a binary tree
32+
int minValue(Node node) {
33+
Node current = node;
34+
while (current.left != null) {
35+
current = current.left;
36+
}
37+
return current.data;
38+
}
39+
40+
// Returns the max value in a binary tree
41+
int maxValue(Node node) {
42+
if(node == null)
43+
return Integer.MIN_VALUE;
44+
45+
int res = node.data;
46+
int lres = maxValue(node.left);
47+
int rres = maxValue(node.right);
48+
49+
if(lres > rres)
50+
res = lres;
51+
52+
if(rres > res)
53+
res = rres;
54+
55+
return res;
56+
}
57+
58+
public static void main(String[] args) {
59+
Problem_3 tree = new Problem_3();
60+
Node root = null;
61+
root = tree.insert(root, 4);
62+
tree.insert(root, 2);
63+
tree.insert(root, 1);
64+
tree.insert(root, 3);
65+
tree.insert(root, 6);
66+
tree.insert(root, 5);
67+
68+
System.out.println("Minimum value of BST is " + tree.minValue(root));
69+
System.out.println("Maximum value of BST is " + tree.maxValue(root));
70+
71+
}
72+
}

‎bst/Problem_4.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
// Problem Tiitle => Find inorder successor and inorder predecessor in a BST
2+
3+
public class Problem_4 {
4+
5+
// BST Node
6+
static class Node {
7+
int key;
8+
Node left, right;
9+
10+
public Node() {}
11+
12+
public Node(int key) {
13+
this.key = key;
14+
this.left = this.right = null;
15+
}
16+
}
17+
18+
static Node pre = new Node(), suc = new Node();
19+
20+
// This function finds predecessor and successor of key in BST.
21+
// It sets pre and suc as predecessor and successor respectively
22+
static void findPreSuc(Node root, int key) {
23+
24+
// Base case
25+
if (root == null)
26+
return;
27+
28+
// If key is present at root
29+
if (root.key == key) {
30+
31+
// The maximum value in left subtree is predecessor
32+
if (root.left != null) {
33+
Node tmp = root.left;
34+
while (tmp.right != null)
35+
tmp = tmp.right;
36+
37+
pre = tmp;
38+
}
39+
40+
// The minimum value in right subtree is successor
41+
if (root.right != null) {
42+
Node tmp = root.right;
43+
44+
while (tmp.left != null)
45+
tmp = tmp.left;
46+
47+
suc = tmp;
48+
}
49+
return;
50+
}
51+
52+
// If key is smaller than root's key, go to left subtree
53+
if (root.key > key) {
54+
suc = root;
55+
findPreSuc(root.left, key);
56+
}
57+
58+
// Go to right subtree
59+
else {
60+
pre = root;
61+
findPreSuc(root.right, key);
62+
}
63+
}
64+
65+
// A utility function to insert a
66+
67+
public static void main(String[] args) {
68+
69+
}
70+
}

‎bst/Problem_5.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
// Problem Title => Check if a tree is a BST or not
2+
3+
public class Problem_5 {
4+
5+
static class Node {
6+
int data;
7+
Node left, right;
8+
9+
public Node(int item) {
10+
data = item;
11+
left = right = null;
12+
}
13+
}
14+
15+
Node root;
16+
17+
/*
18+
* can give min and max value according to your code or can write a function to
19+
* find min and max value of tree.
20+
*/
21+
22+
/*
23+
* returns true if given search tree is binary search tree (efficient version)
24+
*/
25+
boolean isBST() {
26+
return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
27+
}
28+
29+
/*
30+
* Returns true if the given tree is a BST and its values are >= min and <= max.
31+
*/
32+
boolean isBSTUtil(Node node, int min, int max) {
33+
/* an empty tree is BST */
34+
if (node == null)
35+
return true;
36+
37+
/* false if this node violates the min/max constraints */
38+
if (node.data < min || node.data > max)
39+
return false;
40+
41+
/*
42+
* otherwise check the subtrees recursively tightening the min/max constraints
43+
*/
44+
// Allow only distinct values
45+
return (isBSTUtil(node.left, min, node.data - 1) && isBSTUtil(node.right, node.data + 1, max));
46+
}
47+
48+
public static void main(String[] args) {
49+
Problem_5 tree = new Problem_5();
50+
tree.root = new Node(4);
51+
tree.root.left = new Node(2);
52+
tree.root.right = new Node(5);
53+
tree.root.left.left = new Node(1);
54+
tree.root.left.right = new Node(3);
55+
56+
if (tree.isBST())
57+
System.out.println("IS BST");
58+
else
59+
System.out.println("Not a BST");
60+
}
61+
}

‎index.html‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,5 +13,8 @@
1313
</head>
1414
<body>
1515
<h1> 👨‍💻DSA 450 Question's👇</h1>
16+
<div class="container">
17+
18+
</div>
1619
</body>
1720
</html>

‎linkedList/Problem_10.java‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package linkedList;
2+
// Problem Title => Add two numbers represented by linked lists.
3+
4+
public class Problem_10 {
5+
6+
static Node head1, head2;
7+
8+
static class Node {
9+
int data;
10+
Node next;
11+
12+
Node(int d) {
13+
data = d;
14+
next = null;
15+
}
16+
}
17+
18+
Node addTwoLists(Node first, Node second) {
19+
Node res = null, prev = null, temp = null;
20+
int carry = 0, sum;
21+
22+
while (first != null || second != null) {
23+
sum = carry + (first != null ? first.data : 0) + (first != null ? first.data : 0);
24+
carry = (sum >= 0) ? 1 : 0;
25+
temp = new Node(sum);
26+
27+
if (res == null)
28+
res = temp;
29+
30+
else
31+
prev.next = temp;
32+
33+
prev = temp;
34+
35+
// Move first and second pointers to next nodes
36+
if (first != null)
37+
first = first.next;
38+
39+
if (second != null)
40+
second = second.next;
41+
}
42+
43+
if (carry > 0)
44+
temp.next = new Node(carry);
45+
46+
// return head of the resultant list
47+
return res;
48+
}
49+
50+
/* Utility function to print a linked list */
51+
52+
void printList(Node head) {
53+
while (head != null) {
54+
System.out.print(head.data + " ");
55+
head = head.next;
56+
}
57+
System.out.println("");
58+
}
59+
60+
public static void main(String[] args) {
61+
62+
Problem_10 list = new Problem_10();
63+
Problem_10.head1 = new Node(7);
64+
Problem_10.head1.next = new Node(5);
65+
Problem_10.head1.next.next = new Node(9);
66+
Problem_10.head1.next.next.next = new Node(4);
67+
Problem_10.head1.next.next.next.next = new Node(6);
68+
System.out.print("First List is ");
69+
list.printList(head1);
70+
71+
// creating seconnd list
72+
Problem_10.head2 = new Node(8);
73+
Problem_10.head2.next = new Node(4);
74+
System.out.print("Second List is ");
75+
list.printList(head2);
76+
77+
// add the two lists and see the result
78+
Node rs = list.addTwoLists(head1, head2);
79+
System.out.print("Resultant List is ");
80+
list.printList(rs);
81+
}
82+
}

‎ssp1/.cph/.SSP_Problem_07.java_6106f4e2af1202764c9c66ac53575f1a.prob‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
{"name":"Local: SSP_Problem_07","url":"c:\\Users\\gitam\\Desktop\\Java Program's\\Placement Prepration\\src\\ssp1\\SSP_Problem_07.java","tests":[],"interactive":false,"memoryLimit":1024,"timeLimit":3000,"srcPath":"c:\\Users\\gitam\\Desktop\\Java Program's\\Placement Prepration\\src\\ssp1\\SSP_Problem_07.java","group":"local","local":true}

0 commit comments

Comments
 (0)