## binary tree problems with solution

today is saturday and was catching upon some blogs. Then come across some binary tree algorithms and it reminded me the famous stanford binary tree questions.. decided to work on those and got to the mid of it..
Actually the questions get harder as you go further.. the first 7 are relatively easy..
I will continue to work on them and post my solution here.
the solutions are given on the this page but, it is advisable to work them out without looking a the solution..

here it is!

``````
#include
#include
/*
* @author http://gullele.com
* binary tree problems and solutions.
*/
struct Node
{
int number;
struct Node *left;
struct Node *right;
};

struct Node *createNode(int value);
int hasPathSum(struct Node *head, int sum);
int main()
{
struct Node *left=createNode(8);
struct Node *right=createNode(15);
struct Node *right1=createNode(5);
struct Node *right2=createNode(1);
left->left=right1;
right1->left=right2;

struct Node *two=createNode(2);
struct Node *seven=createNode(7);
struct Node *eleven=createNode(11);
struct Node *lfour=createNode(4);
struct Node *thirteen=createNode(13);
struct Node *eight=createNode(8);
struct Node *rfour=createNode(4);
struct Node *one=createNode(1);

lfour->left=eleven;
eleven->left=seven;
eleven->right=two;
eight->left=thirteen;
eight->right=rfour;
rfour->right=one;

printf("Size of the tree is %d n", countNode(head));
printf("Max depth is %d n", maxDepth(head)-1);
printf("Minimum Value is %d n", minValue(head));
printf("n");
if(hasSum)
printf("it has sum");
else
printf("it does not has sum");
return 0;
}

/**
* Takes the head of the binary tree and counts how many children are there in the tree
* it will recursively count the left and right nodes to come to the conclusion
*/
{
{
return 0;
}
}

/**
* Finds the maximum depth of the tree
*
*/
{
int maxLength = 0;
{
return 0;
}
else
{
int leftMax = 1 + maxDepth(head->left);
int rightMax = 1 + maxDepth(head->right);
if (leftMax > rightMax)
{
return leftMax;
}
return rightMax;
}
}

/**
* Works on the Binary Search Tree - since on the BST, for sure the left child is always lesser in value.
*/
{
return 0; //might not be valid answer here
while(current->left!=NULL)
{
current=current->left;
}
return current->number;
}

/**
* Prints the value of the BST
* this is inorder traversal
*/
{
{
return;
}
else
{
}
}

int hasPathSum(struct Node *head, int sum)
{
int localsum = 0;
{
return 0;
}
{
}
else
{
}
}
/**
* Post order traversal version of the tree traversal
*/
{
{
return;
}
else
{
}
}

/**
* Create new node
*/
struct Node *createNode(int value)
{
struct Node *newNode=malloc(sizeof(struct Node));
newNode->number=value;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}

```
```

## gcc complainging warning: incompatible implicit declaration of built-in function â€˜mallocâ€™ [enabled by default]

Working on C code and getting the above warning?
it is as simple as adding

```#include
```

EnjoY!

## Changing decimal number to its binary equivalent

Here is bit level solution to change binary equivalent

```#include

/*
* Printing binary version representation of number
*
* Kaleb Woldeareagy <contactkaleb@gmail.com>
*/

void to_binary(unsigned int x);

void main()
{
unsigned int y=17;
to_binary(y);
}

void to_binary(unsigned int x)
{
if (!x|00)
{
printf("0");
}
else
{
int i=0;
int store[8]; //stack could be used here best
while (x!=0)
{
store[i++]=x&01;
x>>=1;
}

while (i>0)
{
printf("%i", store[--i]);
}
}
}```

## Array reversal in Recurrsion

This problem can be performed in o(n) with normal iterative approach.
Here is vanilla flavor of its implementation in recursion

```#include

/**
* Recursion version of array swap
*
* Kaleb Woldearegay
*/

void reverse(int*arr, int i, int size);
void print(int*arr, int size);

void main()
{
int nums[] = {4,5,2,13,0}, i=0, size=5;
i = 0;
print(nums, 5);
reverse(nums, i, size-1);
print(nums, 5);
}
void reverse(int*stk, int i, int size)
{
if (i>=size)
{
return;
}
else
{
int tmp = stk[i];
reverse(stk, i+1, size-1);
stk[i] = stk[size];
stk[size] = tmp;
}
}

void print(int*nums, int size)
{
int i=0;
while (i<size)
{
printf("%in", nums[i]);
i++;
}
}

```

Here we go

```#include
#include
#include
struct Node
{
char * value;
struct Node *next;
};
struct Node *last = NULL;
char* substr(char*str, int start, int length)
{
const char* from = str;
char *to = (char*) malloc(sizeof(str)/sizeof(char));
strncpy(to, from+start, length);
}

{
struct Node *curr_node = malloc(sizeof(struct Node));
char * newtemp = malloc(strlen(value));
strncpy(newtemp, value, strlen(value));
curr_node->value = newtemp;
curr_node->next = NULL;
{
}
else
{
last->next = curr_node;
last = curr_node;
}

}

{
struct Node * curr_node = head;
while (curr_node !=NULL)
{
printf("%sn", curr_node->value);
curr_node = curr_node->next;
}
}
void main()
{
int delimiter_size = 3, i=0, j=0;
char* delimit = "abc";
char* text = "someabccodingabctoabcparseab";
int length = strlen(text);
char* temp = (char*)malloc(length);
while(i < length)
{
if (text[i] == delimit[0]) //check if the begin
{
//check if the
if (strcmp(substr(text, i, delimiter_size), delimit) == 0)
{
i+=delimiter_size;
j=0;
memset(temp, '', strlen(temp));
continue;
}
}
temp[j] = text[i];
i++;
j++;
}
if (strlen(temp))
{
}
}
```

## Kadane’s algorithm in C – Dynamic Programming

How do we find a keys that hold maximum consecutive values in sum from the given array?
The usual approach could be O(n^2).

But Kadanes algorithm can perform this same problem in a linear time.
here is the implementation using C

``````#include <stdio.h>

/*
* @author http://gullele.com
*
*/
void main()
{
int nums[] = {-1,2,3,-9,8,7,2};
int start_index;
int end_index;
int sum = maximum_consequential_sum(nums, &start_index, &end_index);
printf("maximum sum is %d n",sum );
printf("maximum index starts at %d n", start_index);
printf("maximum index ends at %d n", end_index);
}
/*
* Get the maximum subsequent sum from the given array
*/
int maximum_consequential_sum(int* nums, int*start_index, int*end_index)
{
int max_start_index = 0, max_end_index = 0;
int max_sum = 0;
int cur_index, cur_max_sum = 0;
for(cur_index = 0; cur_index <= max_sum ; cur_index++)
{
cur_max_sum += nums[cur_index];
if (cur_max_sum > max_sum)
{
max_sum = cur_max_sum;
max_end_index = cur_index;
}
if (cur_max_sum < 0)
{
cur_max_sum = 0 ;
max_start_index = cur_index + 1;
}
}
*start_index = max_start_index;
*end_index = max_end_index;
return max_sum;
}
```
```

The above code is, of course, just for illustration purpose. Make sure to check
for empty array and possible division by zero stuff..

To run this on Linux

1. Save the above file as kadanes.c
2. go to terminal and locate to the file