all paths in a tree which sum up to a value

/* From Cracking the Coding Interview 4-8.

You are given a binary tree in which each node contains a value.

 Design an algorithm to print all paths which sum up to that value.

 Note that it can be any path in the tree - it does not have to start at the root. */

/* I use the algorithm suggested in the book for the implementation (with slight improvement). The key point to the algorithm is: On every node, we look “up” to see if we’ve found the sum.

*/

struct node {

    node(int v): value(v), left(nullptr), right(nullptr) { }

    int value;

    node * left, * right;

};

void printPath(vector<int> & v, int i) {

    for (int u = i; u < (int) v.size(); ++u) {

     cout << v[u] << " ";

    }

    cout << endl;

}

void sumInPath(node * n, vector<int> v, const int & sum) {

    if (!n) {

        return;

    }

    v.push_back(n->value);

    int total = 0;

    for (int i = (int) v.size()-1; i >= 0; --i) {

     total += v[i];

     if (total == sum) {

          printPath(v, i);

     }

    }

    if (n->left) {

     sumInPath(n->left, v, sum);

    }

    if (n->right) {

     sumInPath(n->right, v, sum);

    }

}

BST to linked list by depth

/* From Cracking the Coding Interview 4-4.

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i e , if you have a tree with depth D, you’ll have D linked lists)*/

/* The implementation provided in the book works well. It uses O(n) space where n is the number of nodes in the binary search tree.

However, if we are allowed to modify the node struct, we can do it in place. In the new node struct, besides the left and right pointers, we also add a next pointer. Using BFS, we link nodes in each level together and store the head node in a vector. The time complexity is still O(n) and space is O(1). Thanks to Little P for suggesting this solution. 

*/

struct node{

    node(int v = 0);

    node * left;

    node * right;

    node * next;

    int value;

};

node::node(int v): value(v), left(nullptr), right(nullptr), next(nullptr) { }

vector<node *> bst2list(node * root) {

    vector<node *> v;

    queue<node *> q;

    unsigned depth = 0;

    q.push(root);

    while (!q.empty()) {

        node * head = new node();

        v.push_back(head);

        size_t size = q.size();

        node * levelHead = v[depth];

        while (size--) {

             node * n = q.front(); q.pop();

            levelHead->next = new node(n->value);

            levelHead = levelHead->next;

             if (n->left) {

                q.push(n->left);

             }

             if (n->right) {

                q.push(n->right);

            }

        }

        ++depth;

    }

    for (unsigned u = 0; u < v.size(); ++u) {

        node * n = v[u];

        v[u] = v[u]->next;

        delete n;

    }

    return v;

}

remove duplicate characters in a C-style string

/* Ch1_3

 Design an algorithm and write code to remove the duplicate characters in a string with O(1) additional buffer. */

/* This seemingly simple question turns out to be interesting. And I found the solution provided in the book is not quite right.
With the constraint of constant additional buffer, the solution has a O(n^2) running complexity. */

/* The implementation in C++ is slightly different than in java. That’s because C-style string in C/C++ is NUL terminated using special character ‘\0’, while in java a char array is not NUL terminated, and even ‘\0’ count as a char. Below is my implementation in both C++ and in java. */

/* c++ implementation */

void removeDuplicateNoBuffer(char * str) {

    if (!str) {

        return;

    }

    size_t size = strlen(str);

    if (size < 2) {

        return;

    }

    int current = 1;

    while (str[current] != '\0') {

        int i;

        for (i = 0; i < current; ++i) {

            if (str[i] == str[current]) {

                break;

            }

        }

        if (i == current) {

            ++current;

        } else {

            i = current+1;

            while (str[i] != '\0') {

                str[i-1] = str[i];

                ++i;

            }

            str[i-1] = str[i];

        }

    }

}

/* java implementation */

public static void removeDuplicates(char [] str) {

    if (str == null) {

        return;       

    }

    int len = str.length;

    if (len < 2) {

        return;

    }

    int current = 1;

    while (current < len) {

        int j;

        for (j = 0; j < current; ++j) {

            if (str[current] == str[j]) {

                break;

            }

        }

        if (j == current) {

            ++current;

        } else {

            for (j = current+1; j < len-1; ++j) {

                str[j-1] = str[j];

            }

            len--;

            str[len] = 0;

        }

    }

}