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.

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331



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.


13167323410318
20196342965150
630803746422111
537699497121956
80573252437331