Remove the nodes in the binary tree for that the sum of all values from root to leaf is less than K

The easiest way to imagine this problem is to think of this as a sub problem first:

Remove the nodes leafs in the binary tree for that the sum of all values from root to leaf is less than K

In this case, the problem is simple, visit all the leaves, and keep track of the sum of all the parents, such that by the time the leaf node is reached, we will know whether the leaf should be deleted or not.

The below algorithm follows the same pattern, with a little difference. Just that if the leaf is not deleted, the we pass along its value, such that while we return, we can use that to determine whether their parents should stay or not.

Read the algo, its simple to follow.

Terms:

completePath = any path from root to leaf
sumToRoot = sum of all the parent nodes till the root
sumToLeaf = max (sum of all the nodes to the leaf)
completePathSum = max (sum of nodes in completePath)

Algo:

// @return max sum to leaf
int visit(node n, int sumToRoot) {

 if(n == null)
  return 0;
 
 // visit left and right first
 int leftSumToLeaf = visit(n.left, sumToRoot + n.value);
 int rightSumToLeaf = visit(n.right, sumToRoot + n.value);

 int maxSumToLeaf = max(leftSumToLeaf, rightSumToLeaf);
 
 int completePathSum = sumToRoot + n.value + maxSumToLeaf;

 // if completePathSum < k remove and return 0 
 if( completePathSum < k ) {
  delete n;
  return 0;
 }

 // otherwise 
 return n.value + maxSumToLeaf;
}

Do write comments if you feel something is not right. 

Backtracking: Solve Sudoku in Java

This post demonstrates solving Sudoku using Backtracking. Algorithm and a working code sample is given. The code is meant to be self-explanatory, try to understand the code, it 's actually simple.

References:

Backtracking: http://en.wikipedia.org/wiki/Backtracking
Sudoku: http://en.wikipedia.org/wiki/Sudoku

Pre-condition:

# Read input grid (this is in matrix form)
# Grid has 9x9 cells. Cell is represented by (x,y)
# Each cell contains a value from 1 to 9.
# Empty cells are contain the value '0'

Algorithm:

1# solve(cell)
2# If cell not empty, call solve(nextCell)
3# If cell is empty (grid[cell.x][cell.y] == 0)
4# Add value v (v belongs to 1-9)
5# Check if v is valid for cell
6# if not valid, continue to #4
7# If valid, call solve(nextCell)
8# If sudoku solved, return true
9# Else return false

Explanation:

• Create a function solve(currentCell) which takes a cell and returns true/false based on whether the Sudoku is solved or not. 
• Remember if the cell already has a value, there is nothing to do.
• In each call our job is to find a suitable value from 1-9 for the cell, which will solve the sudoku. 
• If we cannot find such value, we backtrack.
• First focus on simple conditions: 
• If currentCell is null, we have reached the end. Return true. (We have solved the problem)
• If currentCell already has a value, no-op (Nothing to do here, call next)
• Now we know currentCell is empty, try each value from 1-9 (checkout the for loop in the code)
• For each value, check if its valid, then put the value else just keep putting next value.
• See if sudoku is solved; if solved, just return true, else return false
• If for loop ends, this means we did not find any valid value for currentCell, something is wrong in the previous value,
• Reset the value to 0, and just return false.

Working Code:

package com.example;

public class Sudoku {

 // dimension of input
 static int N = 9;

 // sample input
 static int grid[][] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, //
   { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, //
   { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, //
   { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, //
   { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, //
   { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, //
   { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, //
   { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, //
   { 0, 0, 5, 2, 0, 6, 3, 0, 0 } };

 /**
  * Class to abstract the representation of a cell. Cell => (x, y)
  */
 static class Cell {

  int row, col;

  public Cell(int row, int col) {
   super();
   this.row = row;
   this.col = col;
  }

  @Override
  public String toString() {
   return "Cell [row=" + row + ", col=" + col + "]";
  }
 };

 /**
  * Utility function to check whether @param value is valid for @param cell
  */

 static boolean isValid(Cell cell, int value) {

  if (grid[cell.row][cell.col] != 0) {
   throw new RuntimeException(
     "Cannot call for cell which already has a value");
  }

  // if v present row, return false
  for (int c = 0; c < 9; c++) {
   if (grid[cell.row][c] == value)
    return false;
  }

  // if v present in col, return false
  for (int r = 0; r < 9; r++) {
   if (grid[r][cell.col] == value)
    return false;
  }

  // if v present in grid, return false

  // to get the grid we should calculate (x1,y1) (x2,y2)
  int x1 = 3 * (cell.row / 3);
  int y1 = 3 * (cell.col / 3);
  int x2 = x1 + 2;
  int y2 = y1 + 2;

  for (int x = x1; x <= x2; x++)
   for (int y = y1; y <= y2; y++)
    if (grid[x][y] == value)
     return false;

  // if value not present in row, col and bounding box, return true
  return true;
 }

 // simple function to get the next cell
 // read for yourself, very simple and straight forward
 static Cell getNextCell(Cell cur) {

  int row = cur.row;
  int col = cur.col;

  // next cell => col++
  col++;

  // if col > 8, then col = 0, row++
  // reached end of row, got to next row
  if (col > 8) {
   // goto next line
   col = 0;
   row++;
  }

  // reached end of matrix, return null
  if (row > 8)
   return null; // reached end

  Cell next = new Cell(row, col);
  return next;
 }

 // everything is put together here
 // very simple solution
 // must return true, if the soduku is solved, return false otherwise
 static boolean solve(Cell cur) {

  // if the cell is null, we have reached the end
  if (cur == null)
   return true;

  // if grid[cur] already has a value, there is nothing to solve here,
  // continue on to next cell
  if (grid[cur.row][cur.col] != 0) {
   // return whatever is being returned by solve(next)
   // i.e the state of soduku's solution is not being determined by
   // this cell, but by other cells
   return solve(getNextCell(cur));
  }

  // this is where each possible value is being assigned to the cell, and
  // checked if a solutions could be arrived at.
  
  // if grid[cur] doesn't have a value
  // try each possible value
  for (int i = 1; i <= 9; i++) {
   // check if valid, if valid, then update
   boolean valid = isValid(cur, i);

   if (!valid) // i not valid for this cell, try other values
    continue;

   // assign here
   grid[cur.row][cur.col] = i;

   // continue with next cell
   boolean solved = solve(getNextCell(cur));
   // if solved, return, else try other values
   if (solved)
    return true;
   else
    grid[cur.row][cur.col] = 0; // reset
   // continue with other possible values
  }

  // if you reach here, then no value from 1 - 9 for this cell can solve
  // return false
  return false;
 }

 public static void main(String[] args) {
  boolean solved = solve(new Cell(0, 0));
  if (!solved) {
   System.out.println("SUDOKU cannot be solved.");
   return;
  }
  System.out.println("SOLUTION\n");
  printGrid(grid);
 }

 // utility to print the grid
 static void printGrid(int grid[][]) {
  for (int row = 0; row < N; row++) {
   for (int col = 0; col < N; col++)
    System.out.print(grid[row][col]);
   System.out.println();
  }
 }
}