Up to date

public class AVLTree { private static Node root; static Node insert(Node node, int data) { // if node is null then create a node and return if(node == null) { return new Node(data); } else if(data < node.data) { // insert into left sub tree node.left = insert(node.left, data); } else if(data > node.data) { // insert into right sub tree node.right = insert(node.right, data); } // set height of current node node.height = getHeightOfNode(node); // check the balance factor to perform rotation of tree if(getBalanceFactor(node) == 2) { if(getBalanceFactor(node.left) == 1) { return performLLRotation(node); } else if(getBalanceFactor(node.left) == -1) { return performLRRotation(node); } } else if(getBalanceFactor(node) == -2) { if(getBalanceFactor(node.rig

It's height balanced tree Height is balanced by balance factor. Balance factor (BF) = height of left sub tree - height of right sub tree Valid FB values = {-1, 0, 1}. BF = |lh-rh| <= 1 Node is balanced if |lh-rh| <= 1 Node is unbalanced if |lh-rh| > 1 All rotations : 1. Left Left (LL) Rotation 2. Right Right (RR) Rotation 3. Left Right (LR) Rotation 4. Right Left (RL) Rotation Idea behind rotations : Insert and delete program   Height vs Node analysis

Reference import java.util.ArrayDeque; class ConstructBSTGivenPreorder { private static Node root; static void constructFromPreorderIterative(int[] preorder) { // create root root = new Node(preorder[0]); // create statck to track left child of tree during construction of tree ArrayDeque stack = new ArrayDeque<>(); // taking variable to track current node Node current = root; // insert all elements for(int i = 1; i < preorder.length; i++) { // create a new node Node node = new Node(preorder[i]); if(node.data < current.data) { current.left = node; stack.addFirst(current); current = node; } else if(stack.isEmpty() || node.data < stack.peekFirst().data) { current.right = node; current = node; } else {

Reference import java.util.ArrayDeque; class BinaryTree { private static Node root; static Node insertRecursive(Node current, Node previous, int data) { if(current == null) { Node node = new Node(data); if(previous == null) { // it's first node in tree return node; } else if(data < previous.data) { // insert into left child previous.left = node; } else { previous.right = node; } return previous; } if(data < current.data) { return insertRecursive(current.left, current, data); } return insertRecursive(current.right, current, data); } static Node insertRecursive2(Node current, int data) { if(current == null) { return new Node(data); } if(data < current.data) { current.left = insertRecursive2(curr

import java.util.ArrayDeque; class SearchTree { static boolean searchRecursive(Node root, int data) { // base check if(root == null) { return false; } else if(root.data == data) { return true; } else if(data < root.data) { return searchRecursive(root.left, data); } else { return searchRecursive(root.right, data); } } static boolean search(Node root, int data) { if(root != null) { while(root != null) { if(root.data == data) { return true; } root = data < root.data ? root.left : root.right; } } return false; } static Node populateTree() { Node root = new Node(4); root.left = new Node(2); root.right = new Node(6); root.left.left = new Node(0); root.left.right = new Node(3); root.right.left

import java.util.ArrayDeque; class ConstructTree { static int count(Node root) { if(root != null) { int leftCount = count(root.left); int rightCount = count(root.right); return leftCount + rightCount + 1; } return 0; } static Node construct(int[] preOrder, int[] inOrder) { // base check if (preOrder.length == 0 || preOrder.length != inOrder.length) { return null; } // counters int preOrderIndex = 0; int inOrderIndex = 0; ArrayDeque stack = new ArrayDeque<>(); Node root = new Node(preOrder[preOrderIndex]); stack.addFirst(root); preOrderIndex++; while(!stack.isEmpty()) { Node top = stack.peekFirst(); if(top.data == inOrder[inOrderIndex]) { stack.pollFirst(); inOrderIndex++; //

Iterative version reference. import java.util.ArrayDeque; class ConstructTree { static Node construct(int[] preOrder, int[] inOrder) { // base check if (preOrder.length == 0 || preOrder.length != inOrder.length) { return null; } // counters int preOrderIndex = 0; int inOrderIndex = 0; ArrayDeque stack = new ArrayDeque<>(); Node root = new Node(preOrder[preOrderIndex]); stack.addFirst(root); preOrderIndex++; while(!stack.isEmpty()) { Node top = stack.peekFirst(); if(top.data == inOrder[inOrderIndex]) { stack.pollFirst(); inOrderIndex++; // if all the elements in inOrder have been visted, we are done if (inOrderIndex == inOrder.length) { break; } // Check if th

Iterative version. import java.util.concurrent.atomic.AtomicInteger; import java.util.Map; import java.util.HashMap; class ConstructTree { static Node constructRecursive(int[] preorder, Map inorderElementMap, AtomicInteger inorderCounter, int inStartIndex, int inEndIndex) { // Corner case for leaf nodes if(inStartIndex > inEndIndex) { return null; } Node root = new Node(preorder[inorderCounter.getAndIncrement()]); // get the root node index in sequence `inorder[]` to determine the // left and right subtree boundary int index = inorderElementMap.get(root.data); // construct left sub-tree root.left = constructRecursive(preorder, inorderElementMap, inorderCounter, inStartIndex, index-1); // construct right sub-tree root.right = constructRecursive(preorder, inorderElementMap, inorderCounter, index+1, inEndIndex);

import java.util.Queue; import java.util.LinkedList; class LevelOrderTreeTraversal { private static Node root; void leverOrderUsingQueue(Node root) { if(root == null) { return; } Queue queue = new LinkedList<>(); queue.add(root); Node current; while(!queue.isEmpty()) { // dequeue from queue current = queue.poll(); System.out.print(current.data + " "); // enqueue left node if(current.left != null) { queue.add(current.left); } // enqueue right node if(current.right != null) { queue.add(current.right); } } } /** * Time to print n levels is O(n^2) */ void leverOrderUsingRecursion(Node root) { if(root == null) { return; } int height = height(root); for(int i = 0; i <

import java.util.Stack; class BinaryTree { private static Node root; /** * a) print it * b) push its right child * c) push its left child */ void preOrder(Node root) { if(root != null) { Stack stack = new Stack<>(); Node current; stack.push(root); while(!stack.empty()){ // Pop the top item from stack and print it current = stack.pop(); System.out.print(current.data + " "); // Push right and left children of the popped node to stack if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } } } void inOrder(Node root) { if(root == null) { return; } Stack stack = new Stack<>();

class BinaryTree { private static Node root; void preOrder(Node root) { if(root != null) { System.out.print(root.data + " "); preOrder(root.left); preOrder(root.right); } } void inOrder(Node root) { if(root != null) { inOrder(root.left); System.out.print(root.data + " "); inOrder(root.right); } } void postOrder(Node root) { if(root != null) { postOrder(root.left); postOrder(root.right); System.out.print(root.data + " "); } } public static void main (String[] args) { BinaryTree tree = new BinaryTree(); 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.left = new Node(6); root.right.right = new Node(7);

  Method 1:  Method 2 :  1.  Recursive Program 2. Iterative Program - Stack 3. Iterative Program - Morris 4. Level Order Traversal

 A binary tree of height "h" having maximum number of nodes is called full binary tree. When a binary tree is represented in an array and there is no blank spaces in the tree between the nodes then tree is called complete binary tree . Or, A complete binary tree of height h will be a full binary tree upto height (h-1). 1. A full binary tree is always a complete binary tree 2. To represent a tree in an array we should have complete binary tree else there will be empty spaces between elements. Strict binary tree has 0 or 2 nodes. Strict binary tree may or may not be complete binary tree.

 

A tree that can have maximum m child nodes is called m-ary tree. Strict m-ary tree : A tree must have all nodes with either 0 or m child nodes. Nodes vs Height of m-ary tree :  Internal Nodes vs External Nodes : Number of external nodes = (m-1) * internal nodes + 1

 A binary tree that has all nodes with exactly 0 or 2 child nodes is called strict binary tree. Height vs Nodes :  Internal Nodes vs External Nodes :  Number of external nodes = Number of internal nodes + 1

 Tree : Tree is collection of nodes and edges. Or, it's collection of nodes where one node is taken as root node and rest of the nodes are divided into disjoint subsets and each subset is tree or subtree.  Tree terminologies :  Level starts from 1 onwards (we count nodes) and height starts from 0 onwards (we counts edges).  Binary Tree : A tree that can have 0, 1 or 2 sub trees, is called binary tree. How many binary trees can be generated from given number of nodes (n)? 1. Unlabelled Nodes : How many trees with maximum height? 2. Labelled Nodes :  Height vs Nodes Formula :  1. If height of binary tree is given? Minimum No. of Nodes (n) = h + 1 Maximum No. of Nodes (n) = 2^(n+1) - 1 2. If nodes of binary tree is given? Minimum Height (h) = log(n+1) - 1 Maximum  Height (h)  = n-1 Relationship b/w nodes with degree 0 and degree 2: Number of nodes with degree(0) = Number of nodes with degree(2) + 1

import java.util.Arrays; /** * Key points : * 1. Max capecity can be size-1. As 1 space in queue will alway be empty * 2. Next index = (currentIndex+1)%size * 3. Empty condition : front == rear * 4. Full condition : (front+1)%size == rear */ class CircularQueue { // for dequeue operation private int front; // for enqueue operation private int rear; private int capacity; private int[] array; private static final int DEFAULT_CAPACITY = 6; // we can insert 5 elements public CircularQueue() { this(DEFAULT_CAPACITY); } public CircularQueue(int capacity) { this.front = this.rear = 0; this.capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity; array = new int[capacity]; } public void enqueue(int data) { if(isFull()) { System.out.println(data + " is not inserted. Queue is full"); } else { rear = (rear + 1) % capacity;

Circular Queue implementation Dequeue : Insert and delete from both front and rear Java Queue hierarchy  

The key difference between SSO and FIM is while SSO is designed to authenticate a single credential across various systems within one organization, federated identity management systems offer single access to a number of applications across various enterprises. So, while SSO is a function of FIM, having SSO in place won’t necessarily allow for federated identity management. That said, both tools are crucial in supporting organizations with both securing their data and minimizing obstacles in user experience. Example : Using SSO I can access all the systems (helpdesk, finance tool, people portal, knowledge portal etc) in an organization. Using FIM I can use my gmail login to sign in to Udemy, zoom etc.

import java.util.Stack; class EvaluationPostfixExpression { static int evaluatePostfix(String postfix) { // stack to store operand Stack stack = new Stack<>(); int ex1, ex2, result; int i = 0; while(i < postfix.length()) { char ch = postfix.charAt(i); if(isOperand(ch)) { // if it's operand then add into stack stack.push(Character.getNumericValue(ch)); } else { // pop 2 values from stack and apply operator and //store result back to stack ex2 = stack.pop(); ex1 = stack.pop(); result = 0; // default value switch(ch) { case '+': result = ex1 + ex2; break; case '-': result = ex1 - ex2; break; ca

  import java.util.Stack; class InfixToPostfix { static String toPostfix(String infix) { // stack to store operators Stack stack = new Stack<>(); StringBuilder result = new StringBuilder(); // store final result int i = 0; while(i < infix.length()) { char ch = infix.charAt(i); if(isOperand(ch)) { // if it's operand then add into result result.append(ch); i++; } else { // deal with operator if(!stack.empty() && getPrecedence(/*ch=*/ch, /*isOperatorFromStack=*/false) == getPrecedence(/*ch=*/stack.peek(), /*isOperatorFromStack=*/true)) { // we got ')' outside stack and '(' inside stack i++; continue; }else if(stack.empty() || getPrecedence(/*ch=*/ch, /*isOperatorFromStack=*/false)

import java.util.Stack; class InfixToPostfix { static String toPostfix(String infix) { // stack to store operators Stack stack = new Stack<>(); StringBuilder result = new StringBuilder(); // store final result int i = 0; while(i < infix.length()) { char ch = infix.charAt(i); if(isOperand(ch)) { // if it's operand then add into result result.append(ch); i++; } else { // deal with operator if(stack.empty() || getPrecedence(ch) > getPrecedence(stack.peek())) { // precendence of input operator is greater than operator // at stack top then add input operator to stack stack.push(ch); i++; } else { // precendence of input operator is <= precendence of stack top // operator s

import java.util.Stack; import java.util.EmptyStackException; import java.util.Optional; class ParenthesisMatching { static boolean isBalanced(Optional equationOptional) { // if input is null or empty return false if(!equationOptional.isPresent()) { return false; } // convert string to char array char[] chars = equationOptional.get().toCharArray(); // create stack Stack stack = new Stack<>(); for(char ch : chars) { try { if(ch == '(') { stack.push('('); } else if(ch == ')') { stack.pop(); // return throws EmptyStackException if stack is empty } } catch(EmptyStackException e) { return false; } } return stack.empty() ? true : false; } public static void main(String[] args) { // positive case Strin

 Greeks problems

 Greeks problems

 Greeks problems

  Reference Problems

Greeks Reference1    Greeks Reference2

Greeks reference . /** * Two approaches can be used here : * 1. Take fast and slow pointer. Slow pointer move 1 step ahead and fast pointer moves * 2 steps ahead. When fast pointer reached last then slow reaches to middle * 2. Traverse to floor(size of linkedlist)/2 nodes or Traverse to ceil(size of * linkedlist)/2 nodes based on demand. */ class FindMiddleOfLinkedList { static Node head; static int findMiddle() { Node slow, fast; slow = fast = head; while(fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow.data; } static void create(int[] data) { head = new Node(); head.data = data[0]; Node last = head; for(int i = 1; i < data.length; i++) { Node temp = new Node(); temp.data = data[i]; last.next = temp; last = temp; } } public

Need to run and correct few errors in output import java.util.*; import java.lang.*; import java.io.*; class SinglyLinkedList { private static Node head; private static Node last; private static void create(int[] data) { // create first Node head = new Node(null, data[0], null); // if only single element if(data.length == 1) { return; } Node last = head; for(int i = 1; i < data.length; i++) { Node newNode = new Node(last, data[i], null); last.setNext(newNode); // reset last node last = newNode; } SinglyLinkedList.last = last; } private static void display() { if(head == null) { System.out.println("No nodes to print in linkedlist"); return; } Node current = head; while(current != null) { System.out.print(" " + current.data); // m

1. Singly LinkedList  2. Circular LinkedList 3. Doubly LinkedList 4. Circular Doubly LinkedList 5. Applications

No node can have null in circular linked list. class CircularSinglyLinkedList { private static Node head; private static void create(int[] data) { // if data is empty early return if(data.length == 0) { return; } // create first node head = new Node(data[0], null); // point next as self head.setNext(head); Node last = head; // add node 2 to n for(int i = 1; i < data.length; i++) { Node newNode = new Node(data[i], head); last.setNext(newNode); last = newNode; } } private static void display() { if(head == null) { return; } Node current = head; do { System.out.print(" " + current.getData()); current = current.getNext(); } while(current != head); } private static void displayRecursive(Node current, boolean flag) { if(cu