## Wednesday, February 8, 2012

### [Amazon Online Test] : Finding the inorder successor

Given a binary search tree with the following node structure

struct tree {
int data;
struct tree *left;
struct tree *right;
struct tree *next;
};
The next pointer of each node is pointing to null.
Write a code to initialize the next pointer of each node to its inorder successor.

Approach:

Traverse in the BST in reverse inorder manner(i.e. postorder) and initialize the inorder successor as the last element visted.

Below piece of code initializes the next element to the inorder successor.

```void inorder_successor(struct node * root) {
static struct node * current = NULL;
if(root == NULL)
return;
inorder(root->right);
root->next = current;
current = root;
inorder(root->left);
return;
}
```

## Thursday, February 2, 2012

### Euler problem : Finding the minimum sum

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

This can be solved by an easy application of the DP.
A nice variation of the  above problem is to find the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331