Posted tagged ‘C’

K distance nodes in a Binary tree

February 3, 2012

For a Given node of a binary tree, print the K distance nodes.

For the solution, you can also refer to stackoverflow. This also tells that only one ancestor can be at K distance from a given node.

Source code: (written in C)

void K_dist_children(node * nd, int K)
{
// Base case
// The Kth child found
if(K==0)
{
printf("%d\n", nd->val);
return;
}

// K distance node from nd are at
// K-1 distance from children of current node
K_dist_children(nd->left, K-1);
K_dist_children(nd->right, K-1);
}

int K_dist_ancestor(node * cur,    //curent node
node * search, //node being searched
int K)
{
// If the node is found, return back the result
if (cur == search)
{
return K-1;
}

int n1, n2;

// recursively search for the node in the tree
n1 = K_dist_ancestor(cur->left, search, K);
n2 = K_dist_ancestor(cur->right, search, K);

// PS: n1 & n2 can't be non-(-1) at the same time

// if node found in any of the sub trees
if((n1 == -1) && (n2 == -1))
return -1;

// node found in right subtree
if((n1 == -1))
{
// the current node is at distance K
if(n2 == 0)
printf("%d", cur->val);

// return back the distance
return (n2-1);
}

// node found in left subtree
if((n2 == -1))
{
// the current node is at distance K
if(n1 == 0)
printf("%d", cur->val);

// return back the distance
return (n1-1);
}
}

void print_K_distance_nodes(node * root, node * search, int K)
{
// The structure of node is:
// struct node{
// int val;
// node * left;
// node * right;
// }

// Print the ancestor at distance K
K_dist_ancestor(root, search, K);

// Print the children at distance K
K_dist_children(search, K);
}

N – QUEEN Backtracking problem solved

November 9, 2011

This all started when I started doubting my coding and downloaded the code from geeksforgeeks for this N-Queen problem. I told one of my friends that I am gonna read it and understand. Then he told me that the problem is quite easy to code, just see the wiki (actually he and me were interested more in the animation on that page 😉

Anyhow the wiki pages : Eight Queen , Backtracking were not of much use as they were not giving good pseudo code. But this here, see it and try to think, what all can I need for the N – Queen problem..

Enough of waiting now, here is the C++ code for the problem I wrote.

#include<iostream>
using namespace std;

/** this is the size of chess board */
#define N 8

/** Given a completed board, this prints it to the stdout */
void print_solution(int state[N][N])
{
int i,j;
for(i=0; i<N; ++i)
{
for(j=0; j<N; ++j)
cout<<state[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}

/** return true if placing a queen on [row][col] is acceptable
else return false */
bool accept(int state[N][N], int row, int col)
{
int i,j;

/* check the column */
for (i=0; i<N; ++i)
{
if (state[row][i])
return false;
}

/* check the row */
for (i=0; i<N; ++i)
{
if (state[i][col])
return false;
}

/* check the upper left diagnol */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (state[i][j])
return false;
}

/* check the lower left diagnol */
for (i = row, j = col; i < N && j >= 0; ++i, --j)
{
if (state[i][j])
return false;
}

/* check the upper right diagnol */
for (i = row, j = col; i >= 0 && j < N; i--, ++j)
{
if (state[i][j])
return false;
}

/* check the lower right diagnol */
for (i = row, j = col; i < N && j < N; ++i, ++j)
{
if (state[i][j])
return false;
}

/* return true if all tests passed */
return true;
}

void solve_state(int state[N][N], int row)
{
int i;

/* if all queens have been placed at non conflicting positions */
if (row == N)
{
print_solution(state);
return;
}

/* Place queens on all positions in a given row and
check if the state is acceptable
Continue the process till all possibilities found */
for(i=0; i<N; ++i)
{
if(accept(state, row, i))
{
state[row][i] = 1;
solve_state(state, row+1);
}
state[row][i] = 0;
}
}

int main()
{
/* initialise the board */
int state[N][N] = {0};

solve_state (state, 0);

return 0;
}

This code can be easily converted to C, just make amendments to bool values. Rest of the program deals with the board matrix, so C won’t have problems.

Result: Backtracking is pretty easy if you get the idea.


%d bloggers like this: