Home » Data Structure & Algorithms
Category Archives: Data Structure & Algorithms
Inorder predecessor and successor for a given key in Binary Search Tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
package com.ai1tutorial.ds.algo.binary.search.tree; class BinarySearchTree { int data; BinarySearchTree left; BinarySearchTree right; public BinarySearchTree(int data) { this.data = data; this.left = null; this.right = null; } public BinarySearchTree newNode(int data) { BinarySearchTree node = new BinarySearchTree(data); return node; } } public class InorderPredecessorSuccessor { static BinarySearchTree root = null; static BinarySearchTree predecessor = null; static BinarySearchTree successor = null; public static void main(String[] args) { root = new BinarySearchTree(20); root.left = root.newNode(8); root.right = root.newNode(22); root.left.left = root.newNode(4); root.left.right = root.newNode(12); root.left.right.left = root.newNode(10); root.left.right.right = root.newNode(14); int element = 8; inorderPredecessorSuccessor(root, element); if (null != predecessor) { System.out.println("InOrder Predecessor of element " + element + " is " + predecessor.data); } else { System.out.println("No Predecessor found"); } if (null != successor) { System.out.println("InOrder Successor of element " + element + " is " + successor.data); } else { System.out.println("No Successor found"); } } private static void inorderPredecessorSuccessor(BinarySearchTree root, int element) { if (null == root) { return; } if (root.data == element) { if (null != root.left) { BinarySearchTree node = root.left; while (null != node.right) { node = node.right; } predecessor = node; } if (null != root.right) { BinarySearchTree node = root.right; while (null != node.left) { node = node.left; } successor = node; } return; } if (root.data > element) { successor = root; inorderPredecessorSuccessor(root.left, element); } else { predecessor = root; inorderPredecessorSuccessor(root.right, element); } } } |
|
1 2 |
InOrder Predecessor of element 8 is 4 InOrder Successor of element 8 is 10 |
maximum number of 1 in a row of a matrix
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
package com.ai1tutorial.ds.algo.matrix; public class RowWithMaxOneMatrix { public static void main(String[] args) { int matrix[][] = { { 0, 0, 1, 1, 1 }, { 0, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0 }, }; int resultIndex = rowWithMaxOneMatrix(matrix); if (resultIndex == -1) { System.out.println("There are no rows present with 1"); } else { System.out.println("Row number " + (resultIndex + 1) + " has the maximum number of 1s"); } } private static int rowWithMaxOneMatrix(int[][] matrix) { int noOfRows = matrix.length; int noOfCols = matrix[0].length; int rowIndex = 0; int currentMax = -1; int index; for (int i = 0; i < noOfRows; i++) { index = binarySearchFirstOne(matrix[i], 0, noOfCols - 1); if (index != -1 && noOfCols - index > currentMax) { currentMax = noOfCols - index; rowIndex = i; } } return rowIndex; } private static int binarySearchFirstOne(int[] arr, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == 0 || arr[mid - 1] == 0) && arr[mid] == 1) { return mid; } else if (arr[mid] == 0) { return binarySearchFirstOne(arr, mid + 1, high); } else { return binarySearchFirstOne(arr, low, mid - 1); } } return -1; } } |
|
1 |
Row number 2 has the maximum number of 1s |
Height or Maximum depth of a Binary Tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
package com.ai1tutorial.ds.algo.binary.tree; class BinaryTree { int data; BinaryTree left; BinaryTree right; public BinaryTree(int data) { this.data = data; this.left = null; this.right = null; } } public class MaxHeightOrMaxDepth { static BinaryTree root = null; public static void main(String[] args) { root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); root.left.right.left = newNode(10); root.left.right.right = newNode(11); root.right.left.left = newNode(12); root.right.left.right = newNode(13); root.right.right.left = newNode(14); root.right.right.right = newNode(15); System.out.println("Height or Max depth of Binary Tree is : " + heightOrMaxDepth(root)); } private static BinaryTree newNode(int data) { return new BinaryTree(data); } private static int heightOrMaxDepth(BinaryTree root) { if (null == root) { return 0; } int leftHeight = heightOrMaxDepth(root.left); int rightHeight = heightOrMaxDepth(root.right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } } |
|
1 |
Height or Max depth of Binary Tree is : 4 |
Print nodes which are at k distance from root
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
package com.ai1tutorial.ds.algo.binary.tree; class BinaryTree{ int data; BinaryTree left; BinaryTree right; public BinaryTree(int data){ this.data = data; this.left = null; this.right = null; } } public class KDistantNodes { static BinaryTree root = null; public static void main(String[] args){ root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); root.left.right.left = newNode(10); root.left.right.right = newNode(11); root.right.left.left = newNode(12); root.right.left.right = newNode(13); root.right.right.left = newNode(14); root.right.right.right = newNode(15); printKDistantNodes(root,3); } private static BinaryTree newNode(int data) { return new BinaryTree(data); } private static void printKDistantNodes(BinaryTree root, int k) { if (null == root) { return; } if (k == 0) { System.out.print(root.data + " "); return; } else { printKDistantNodes(root.left, k - 1); printKDistantNodes(root.right, k - 1); } } } |
|
1 |
8 9 10 11 12 13 14 15 |
In place Rotation of square matrix by 90 degrees
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package com.ai1tutorial.ds.algo.matrix; public class RotateMatrixBy90Degrees { public static void main(String[] args) { int matrix[][] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, }; System.out.println("Original Matrix"); printMatrix(matrix); System.out.println("90 degree Rotated Matrix"); printSprialMatrix(matrix); } private static void printMatrix(int[][] matrix) { int noOfRows = matrix.length; int noOfCols = matrix[0].length; for (int i = 0; i < noOfRows; i++) { for (int j = 0; j < noOfCols; j++) { System.out.print(matrix[i][j] + "\t"); } System.out.println(); } } private static void printSprialMatrix(int[][] matrix) { int noOfRows = matrix.length; for (int i = 0; i < noOfRows / 2; i++) { for (int j = i; j < noOfRows - i - 1; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][noOfRows - 1 - i]; matrix[j][noOfRows - 1 - i] = matrix[noOfRows - 1 - i][noOfRows- 1 - j]; matrix[noOfRows - 1 - i][noOfRows - 1 - j] = matrix[noOfRows- 1 - j][i]; matrix[noOfRows - 1 - j][i] = temp; } } printMatrix(matrix); } } |
|
1 2 3 4 5 6 7 8 9 10 |
Original Matrix 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 90 degree Rotated Matrix 4 9 14 19 5 3 8 13 18 10 2 7 12 17 15 1 6 11 16 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
package com.ai1tutorial.ds.algo.matrix; public class SpriralMarixPrint { public static void main(String[] args) { int matrix[][] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, }; printSprialMatrix(matrix); } private static void printSprialMatrix(int[][] matrix) { if (null == matrix) { return; } int noOfRows = matrix.length; int noOfCols = matrix[0].length; int i; int row_start = 0; int row_end = noOfRows; int col_start = 0; int col_end = noOfCols; while (row_start < row_end && col_start < col_end) { for (i = col_start; i < col_end; ++i) { System.out.print(matrix[row_start][i] + "\t"); } row_start++; for (i = row_start; i < row_end; ++i) { System.out.print(matrix[i][col_end - 1] + "\t"); } col_end--; if (row_start < row_end) { for (i = col_end - 1; i >= col_start; --i) { System.out.print(matrix[row_end - 1][i] + "\t"); } row_end--; } if (col_start < col_end) { for (i = row_end - 1; i >= row_start; --i) { System.out.print(matrix[i][col_start] + "\t"); } col_start++; } } } } |
|
1 |
1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12 |
Print matrix in Spiral form
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
package com.ai1tutorial.ds.algo.matrix; public class SpriralMarixPrint { public static void main(String[] args) { int matrix[][] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, }; printSprialMatrix(matrix); } private static void printSprialMatrix(int[][] matrix) { if (null == matrix) { return; } int noOfRows = matrix.length; int noOfCols = matrix[0].length; int i; int row_start = 0; int row_end = noOfRows; int col_start = 0; int col_end = noOfCols; while (row_start < row_end && col_start < col_end) { for (i = col_start; i < col_end; ++i) { System.out.print(matrix[row_start][i] + "\t"); } row_start++; for (i = row_start; i < row_end; ++i) { System.out.print(matrix[i][col_end - 1] + "\t"); } col_end--; if (row_start < row_end) { for (i = col_end - 1; i >= col_start; --i) { System.out.print(matrix[row_end - 1][i] + "\t"); } row_end--; } if (col_start < col_end) { for (i = row_end - 1; i >= row_start; --i) { System.out.print(matrix[i][col_start] + "\t"); } col_start++; } } } } |
|
1 |
1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12 |
Search an element in a row wise and column wise sorted matrix
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package com.ai1tutorial.ds.algo.matrix; public class SearchElementMain { public static void main(String[] args) { int matrix[][] = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, }; int element = 13; if (!searchInSortedMatrix(matrix, element)) { System.out.println("Element " + element + " not found in matrix"); } } private static boolean searchInSortedMatrix(int[][] matrix, int element) { if (null == matrix) { return false; } int noOfRows = matrix.length; int noOfCols = matrix[0].length; int i = 0; int j = noOfCols - 1; while (i < noOfRows && j >= 0) { if (matrix[i][j] == element) { System.out.println("Element " + element + " found in matrix at (" + i + "," + j + ") index position"); return true; } if (matrix[i][j] > element) { j--; } else { i++; } } return false; } } |
|
1 |
Element 13 found in matrix at (2,2) index position |
Postorder Binary Tree Traversal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
package com.ai1tutorial.ds.algo.binary.tree; import java.util.Stack; class BinaryTreeNode{ int data; BinaryTreeNode left; BinaryTreeNode right; public BinaryTreeNode(int data){ this.data = data; this.left = null; this.right = null; } } public class PostOrderTraversalMain { static BinaryTreeNode root = null; public static void main(String[] args){ root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); root.left.right.left = newNode(10); root.left.right.right = newNode(11); root.right.left.left = newNode(12); root.right.left.right = newNode(13); root.right.right.left = newNode(14); root.right.right.right = newNode(15); recursivePostOrder(root); iterativePostOrderWithStack(root); } private static BinaryTreeNode newNode(int data) { return new BinaryTreeNode(data); } private static void recursivePostOrder(BinaryTreeNode root) { if (null == root) { return; } // traverse in Left->Right->Root order recursivePostOrder(root.left); recursivePostOrder(root.right); System.out.print(root.data + "\t"); } private static void iterativePostOrderWithStack(BinaryTreeNode root) { if (null == root) { return; } Stack<BinaryTreeNode> stack1 = new Stack<BinaryTreeNode>(); Stack<BinaryTreeNode> stack2 = new Stack<BinaryTreeNode>(); BinaryTreeNode node; stack1.push(root); while (!stack1.isEmpty()) { node = stack1.peek(); stack1.pop(); stack2.push(node); if (null != node.left) { stack1.push(node.left); } if (null != node.right) { stack1.push(node.right); } } System.out.println();//just to print the below output in a new line while (!stack2.isEmpty()) { node = stack2.peek(); stack2.pop(); System.out.print(node.data + "\t"); } } } |
|
1 2 |
8 9 4 10 11 5 2 12 13 6 14 15 7 3 1 8 9 4 10 11 5 2 12 13 6 14 15 7 3 1 |
Root to leaf path sum in Binary Tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
package com.ai1tutorial.ds.algo.binary.tree; class BinaryTree { int data; BinaryTree left; BinaryTree right; public BinaryTree(int data) { this.data = data; this.left = null; this.right = null; } } public class RootToLeafPathSum { static BinaryTree root = null; public static void main(String[] args) { root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); root.left.right.left = newNode(10); root.left.right.right = newNode(11); root.right.left.left = newNode(12); root.right.left.right = newNode(13); root.right.right.left = newNode(14); root.right.right.right = newNode(15); printRootToLeafPathSum(root); } private static BinaryTree newNode(int data) { return new BinaryTree(data); } private static void printRootToLeafPathSum(BinaryTree root) { int path[] = new int[1000]; recurPrintRootToLeafPathSum(root, path, 0); } private static void recurPrintRootToLeafPathSum(BinaryTree root, int[] pathArray, int index) { if (null == root) { return; } pathArray[index++] = root.data; if (null == root.left && null == root.right) { printPathArray(pathArray, index); } else { recurPrintRootToLeafPathSum(root.left, pathArray, index); recurPrintRootToLeafPathSum(root.right, pathArray, index); } } private static void printPathArray(int[] pathArray, int index) { System.out.print("Root to Leaf Path Sum "); for (int i = 0; i < index; i++) { System.out.print(pathArray[i] + "\t"); } System.out.println(); } } |
|
1 2 3 4 5 6 7 8 |
Root to Leaf Path Sum 1 2 4 8 Root to Leaf Path Sum 1 2 4 9 Root to Leaf Path Sum 1 2 5 10 Root to Leaf Path Sum 1 2 5 11 Root to Leaf Path Sum 1 3 6 12 Root to Leaf Path Sum 1 3 6 13 Root to Leaf Path Sum 1 3 7 14 Root to Leaf Path Sum 1 3 7 15 |
Left View of a Binary Tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
package com.ai1tutorial.ds.algo.binary.tree; class BinaryTree { int data; BinaryTree left; BinaryTree right; public BinaryTree(int data) { this.data = data; this.left = null; this.right = null; } } public class LeftViewBinaryTree { static BinaryTree root = null; static int currentLevel = 0; public static void main(String[] args) { root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); root.left.right.left = newNode(10); root.left.right.right = newNode(11); root.right.left.left = newNode(12); root.right.left.right = newNode(13); root.right.right.left = newNode(14); root.right.right.right = newNode(15); int level = 1; System.out.print("Left View of Binary Tree "); printLeftViewBinaryTree(root, level); } private static BinaryTree newNode(int data) { return new BinaryTree(data); } private static void printLeftViewBinaryTree(BinaryTree root, int level) { if (null == root) { return; } if (currentLevel < level) { System.out.print(root.data+"\t"); currentLevel = level; } printLeftViewBinaryTree(root.left, level + 1); printLeftViewBinaryTree(root.right, level + 1); } } |
|
1 |
Left View of Binary Tree 1 2 4 8 |