Vertical Order Traversal of Tree

Java Program using HashMap:

public class TreeTraversalPrograms {
    private static Map<Integer, List<TreeNode>> treeNodeVerticalLevelMap = new TreeMap<>();

    public static void main(String[] args) {
        // Tree construction
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.right.left.right = new TreeNode(8);
        root.right.right.right = new TreeNode(9);

        verticalOrderTraversal(root, 0);
        SortedSet<Integer> keys = new TreeSet<Integer>(treeNodeVerticalLevelMap.keySet());
        for (Integer key : keys) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(key);
            for (TreeNode treeNode : treeNodesList) {
                System.out.print(treeNode.data + ",");
            }
            System.out.println();
        }
    }
    public static void verticalOrderTraversal(TreeNode node, int width) {
        if (node == null) {
            return;
        }
        if (treeNodeVerticalLevelMap.containsKey(width)) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(width);
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        } else {
            List<TreeNode> treeNodesList = new ArrayList<>();
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        }
        if (node.left != null) {
            verticalOrderTraversal(node.left, width - 1);
        }
        if (node.right != null) {
            verticalOrderTraversal(node.right, width + 1);
        }
    }
}

Sample Output:

4,
2,
1,5,6,
3,8,
7,
9,

Find if a word is present in a matrix

Find if all the characters of a given word is present in a two dimensional matrix if the matrix can be traversed as described in the image below:

Java Program:

public class MatrixTraversalPrograms {
 public boolean driverForIsWordPresent(char[] in, char[][] matrix) {
  boolean wordFound = false;
  for(int i=0;i<matrix.length;i++) {
   for(int j=0;j<matrix[i].length;j++) {
    if(in[0] == matrix[i][j]) {
     wordFound = isWordPresent(in, matrix, i, j, 0);
    }
    if(wordFound) {
     break;
    }
   }
   if(wordFound) {
    break;
   }
  }
  return wordFound;
 }
 
 public boolean isWordPresent(char[] in, char[][] matrix, int i, int j, int index) {
  if(index == in.length - 1) {
   return true;
  }
  else {
   boolean complete = false;
   //Top Right
   if(i-1 >= 0 && j+1 < matrix[i].length && matrix[i-1][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Right
   if(!complete && i >= 0 && i < matrix.length && j+1 < matrix[i].length && matrix[i][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom Right
   if(!complete && i+1 < matrix.length && j+1 < matrix[i+1].length && matrix[i+1][j+1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j+1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom
   if(!complete && i+1 < matrix.length && j >= 0 && j < matrix[i+1].length && matrix[i+1][j] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j, index + 1);
    if(complete) {
     return true;
    }
   }
   //Bottom Left
   if(!complete && i+1 < matrix.length && j-1 >= 0 && matrix[i+1][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i+1, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Left
   if(!complete && i>=0 && i < matrix.length && j-1 >= 0 && matrix[i][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Top Left
   if(!complete && i-1 >= 0 && j-1 >= 0 && matrix[i-1][j-1] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j-1, index + 1);
    if(complete) {
     return true;
    }
   }
   //Top
   if(!complete && i-1 >= 0 && j >= 0 && j < matrix[i-1].length && matrix[i-1][j] == in[index+1]) {
    complete = isWordPresent(in, matrix, i-1, j, index + 1);
    if(complete) {
     return true;
    }
   }
   return false;
  }
 }
}

Unit Tests:

import static org.junit.Assert.*;

import org.junit.Test;

import junit.framework.Assert;

public class MatrixTraversalTests {
 
 MatrixTraversalPrograms programInstance = new MatrixTraversalPrograms();
 @Test
 public void testTwoCharacterPresent() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','b'},
   {'a','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoOnePresent() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','c'},
   {'a','x'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoBiggerMatrix() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','x','x'},
   {'x','b','x'},
   {'a','x','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testTwoRepeated() {
  char[] in = {'a','b'};
  char[][] matrix = new char[][]{ 
   {'x','x','x'},
   {'x','b','x'},
   {'a','b','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testLarge() {
  char[] in = {'M','i','c','r','o','s','o','f','t'};
  char[][] matrix = new char[][]{
   {'x','x','x','x','x','x'},
   {'x','r','o','x','x','x'},
   {'x','x','c','s','x','x'},
   {'x','x','i','o','f','x'},
   {'x','M','x','x','f','x'},
   {'x','x','x','t','x','x'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testLargePartialPresent() {
  char[] in = {'M','i','c','r','o','s','o','f','t'};
  char[][] matrix = new char[][]{
   {'x','x','x','x','x','x'},
   {'x','r','o','x','x','x'},
   {'x','x','c','s','x','x'},
   {'x','x','i','o','f','x'},
   {'x','M','x','x','f','x'},
   {'x','x','x','x','x','x'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testOneCharacterPresent() {
  char[] in = {'a'};
  char[][] matrix = new char[][]{
   {'a'}
   };
  Assert.assertTrue(programInstance.driverForIsWordPresent(in, matrix));
 }
 
 @Test
 public void testOneCharacterAbsent() {
  char[] in = {'a'};
  char[][] matrix = new char[][]{
   {'b'}
   };
  Assert.assertFalse(programInstance.driverForIsWordPresent(in, matrix));
 }
}