BFS: Breadth First Search for Trees/Graphs in Java

BFS is easy to understand if explained in Java, than C. The advantage being you can focus on the algorithm rather than the intricacies of the implementation.

Algorithm:

1. Initialize queue (q)
2. Push root node to queue
3. While queue not empty
4. Dequeue n
5. If n == required_node, return n;
6. foreach vertices v of n
7. if v is visited, continue
8. else enque v
9. return null; 

The algorithm might look quite vague. Just follow the code, it will be easy to understand.

Code: BFSDemo.java

package com.example;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class BFSDemo {

 // define node here
 static class Node {

  int value;
  boolean visited = false; // optional
  List vertices = new ArrayList<>();

  public Node(int value) {
   super();
   this.value = value;
  }

  public void addVertex(Node n) {
   vertices.add(n);
  }

  @Override
  public String toString() {
   return "Node [value=" + value + ", visited=" + visited
     + ", vertices=" + vertices + "]";
  }
 };

 public static Node find(Node root, int element) {
  // #1: Initialize queue (q)
  Queue q = new ConcurrentLinkedQueue<>(); // some queue
              // implementation
  // #2: Push root node to queue
  q.add(root);

  // #3: While queue not empty
  while (!q.isEmpty()) {

   // #:4 Dequeue n
   Node n = q.poll();
   // visit this node
   n.visited = true;

   // #5: If n == required_node, return n;
   if (n.value == element)
    return n;

   // #5: foreach vertices v of n
   for (Node v : n.vertices) {
    // #6: if v is visited, continue
    if (v.visited)
     continue;
    // #7: else enque v
    q.add(v);
   }
  }
  // #8: return null;
  return null; // cannot find element
 }

 public static void main(String[] args) {

  // create graph/tree
  Node n1 = new Node(1);
  Node n2 = new Node(2);
  Node n3 = new Node(3);
  Node n4 = new Node(4);
  Node n5 = new Node(5);

  // call traverse
  n1.addVertex(n2);
  n1.addVertex(n3);

  n3.addVertex(n4);
  n3.addVertex(n5);

  Node found = find(n1, 4);
  System.out.println(found); 
  // Node [value=4, visited=true, vertices=[]]
  
  found = find(n1, 7);
  System.out.println(found); 
  // null
 }
}

This logic is same for trees. The difference being: 

• Each node has only 2 children. 
• No need for visited flag in node.

Backtracking: Tug of War

Refer to the question at GFG:
http://www.geeksforgeeks.org/tug-of-war/

The solution given here is much easier to understand and its in Java.

Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.

For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148).

package com.example;

public class TugOfWar {

 static int[] a = { 23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4 };
 static int n = a.length;
 static int minDiff = Integer.MAX_VALUE;
 static boolean[] solution = new boolean[n];
 static boolean[] selected = new boolean[n];

 public static void main(String[] args) {
  solve(0);
  print();
 }

 // the solution is simple,

 // 1. in each iteration, either add or remove the current element from the selected array
 // 2. check if we have already selected the requried number of elements, in that case update solution
 // 3. check if have already reached the end of the array, in that case, simply return
 protected static void solve(int currentIndex) {

  // get size of selected
  int selectedSize = 0;
  for (int i = 0; i < n; i++)
   if (selected[i])
    selectedSize++;

  if (selectedSize == n / 2) {
   // check if diff < minDiff, update solution
   int diff = getDiff();
   if (diff < minDiff) {
    minDiff = diff;
    updateSolution();
   }
  }

  // check if currentIndex == n and return
  if (currentIndex >= n)
   return;

  // add curindex to selected
  selected[currentIndex] = true;
  solve(currentIndex + 1);

  // remove curindex from selected
  selected[currentIndex] = false;
  solve(currentIndex + 1);
 }

 protected static void updateSolution() {
  for (int i = 0; i < n; i++) {
   solution[i] = selected[i];
  }
 }

 protected static void print() {
  for (int i = 0; i < n; i++) {
   if (solution[i]) {
    System.out.print(a[i]);
    System.out.print(",");
   }
  }
  System.out.println();
  for (int i = 0; i < n; i++) {
   if (!solution[i]) {
    System.out.print(a[i]);
    System.out.print(",");
   }
  }
  System.out.println();
 }

 protected static int getDiff() {

  int leftSum = 0;
  int rightSum = 0;

  for (int i = 0; i < n; i++) {
   if (selected[i])
    leftSum += a[i];
   else
    rightSum += a[i];
  }

  return Math.abs(rightSum - leftSum);
 }
}

Inorder successor for BST

Inorder traversal:

left
root
right

Algorithm:

1. Perform inorder traversal.
2. Locate the required node (q) first.
3. if 'q' found, print the next node and exit

#define TRUE 1
#define FALSE 0

void isuccessor(node *p, node *q) {
 
 // used to identify whether the given node is found
 static int is_node_found = FALSE;
 
 // if either of this are null, return
 if( !p || !q) 
  return;
 
 // left sub-tree
 isuccessor(p->left, q);
 
 // root, i.e. logic foreach node is done here
 // already q found, print this node and quit
 if( is_node_found ) {
  printf("%d", node->info);
  exit(0);
 }
 
 // we have found q
 if( q->info == p->info ) {
  is_node_found = TRUE; 
       
 } 
 
 // right sub-tree
 isuccessor(p->right, q);
}

Split linked list on alternate nodes

Pseudocode:

The code is self explanatory.

node* split( node *list) {


 node *p, node *q, node *new;
 
 // we need atleast 2 nodes to split
 if( !list || !list->next )
  return NULL;
  
 // p points to second node
 // q points to first node 
 // q trails p
  
 q = list;
 p = list->next;


 while( p && q ) {


  q->next = p->next;
  
  if( q->next )
   p->next = q->next->next;
  else {
   p->next = NULL;
   break;
  }
  
  // increment pointers
  p = p->next;
  q = q->next;
 }


 return new;
}

Code for Run Length Encoding

Algorithm:

step 1: input string s, char *c
step 2: c = s;
step 3: foreach character *c, in the string s,
step 4: compare subsequent characters *p, if equal, inc counter till *p != *c
step 5: append c and count to enc_string
step 6: reset count to 1
step 7: make c = p;
step 8: end for

Program:

char* encode(char *s) {
 char *c, *p; char enc[100]; int count = 1, i = 0;
 if( s == NULL ) 
  return NULL;
 c = s;


 while( *c ) {
  if( !(*(c+1) ) { //end of string, append c and count
   enc[i++] = c;
   enc[i++] = count;
   count = 1;
   break;
  }
  p = c+1;
  
  while( *p == *c ) {
   p++;
   count++;
  }
  enc[i++] = c;
  enc[i++] = count;
  count = 1;
  c = p;
 }
 return enc;
}

BST post-order Traversal (Recursive Code and Complexity)

Pre-condition:

typedef struct intnode {
 int info;
 node *left, *right; 
}node;

Algorithm:
step 1: if pointer is null, return;
step 2: visit left-sub tree, repeat step 1
step 3: visit right-sub-tree, repeat step 1
step 4: visit root
step 5: stop

Code:

void postorder(node *p){
 // if pointer is null, return
 if( p == NULL )
  return; 
  
 // visit left
 postorder( p->left );
 
 // visit right
 postorder( p->right );
 
 // visit root
 printf("%d ", p->info );
 
 return;
}

Complexity:
O(n), because each node has to be visited atleast once and increases linearly for increasing 'n'.

BST pre-order Traversal (Recursive Code and Complexity)

Pre-condition:

typedef struct intnode {
 int info;
 node *left, *right;
}node;

Algorithm:
step 1: if pointer is null, return;
step 2: visit root
step 3: visit left sub-tree, repeat step 1
step 4: visit right sub-tree, repeat step 1
step 5: stop

Code:

void preorder(node *p){
 // if pointer null, return
 if( p == NULL )
  return; 
  
 // visit root
 printf("%d ", p->info);
 
 // visit left-sub-tree
 preorder( p->left );
 
 // visit right-sub-tree
 preorder( p->right );
}

Complexity:
O(n), because each node has to be visited atleast once and increases linearly for increasing 'n'.