Project 1
BINARY TREE TO DLL
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In -Place. The left and right references in nodes are to be used as previous and next references respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.
Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL .
Expected Time Complexity: O(N).
Expected Space Complexity : O(H). H is the height of the tree and this space is used implicitly for recursion stack.
Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000
public class bToDLL {
public Node bToDLL(Node root) {
if (root == null)
return null;
if (root.left != null) {
Node left = bToDLL(root.left);
for ( left.right !=null; left = left.right);
left.right = root;
root.left = left;
}
if (root.right != null) {
Node right = bToDLL(root.right);
for(; right.left != null; right = right.left)
right.left = root;
root.right = right;
}
return root.left != null ? root.left : root;
}
REVERSE WORDS IN A GIVEN STRING
Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots. Complete the function which takes a string S containing characters and outputs a single line containing the reversed String.
Constraints:
1 <= T <= 100
1 <= |S| <= 2000
public class reverseWords {
public static String reverseWords(String s) {
String[] words = s.split("\\.");
StringBuilder sb = new StringBuilder();
for (int i = words.length -1; i>=0; i--) {
sb.append(words[i]).append(".");
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
}
REMOVE DUPLICATES
Given a string, the task is to remove duplicates from it. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string. Original order of characters must be kept same. Complete the function that takes a string and prints the modified string without duplicates and same order of characters.
Constraints:
1 <= |string|<= 1000
public class removeDuplicates {
public static String removeDuplictaes(String s) {
boolean[] charExists = new boolean[256];
StringBuilder sb = new StringBuilder();
for (int i =0; i<s.length(); i++) {
char c = s.charAt(i);
if(!charExists[c]) {
sb.append(c);
charExists[c]=true;
}
}
return sb.toString();
}
public class Node2 {
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}