Coding Interview Practice: Tree Traversals

traversal.cpp

#include <map>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

//
// Lessons learned:
//
// - correct notation for function pointers
// - callbacks often require additional data to be passed to them to be
//   useful
// - functions need to be declared before they are called
// - return value of calloc needs to be cast to the appropriate type
//   (in C++, C appears to forgive this).  For more details, see:
//   http://stackoverflow.com/questions/3477741/why-does-c-require-a-cast-for-malloc-but-c-doesnt
// - std::find() not vector.find()
// - C++ does not require the explicit "struct" qualifier, leaving it off can
//   make things more readable
// - typedef'ing a callback can make things significantly more readable
// - using malloc in C++ appears to be a sin.  For more details, see:
//   http://stackoverflow.com/questions/184537/in-what-cases-do-i-use-malloc-vs-new
// - classes can be more useful than structs (take advantage of constructor)
// - class members are private by default
//
// Compiles with:
//
// cl traversal.cpp (on Windows using MSVC 2010)
//

class Node 
{
public:
    int value;
    Node *left;
    Node *right;
    Node(int value_)
    {
        value = value_;
        left = NULL;
        right = NULL;
    }
};

void
store_parents(Node *node, void *cb_data);

typedef void (VisitCallback)(Node *node, void *cb_data);

void
preorder(Node *n, VisitCallback *visit, void *cb_data)
{
    visit(n, cb_data);
    if (n->left) preorder(n->left, visit, cb_data);
    if (n->right) preorder(n->right, visit, cb_data);
}

void
inorder(Node *n, VisitCallback *visit, void *cb_data)
{
    if (n->left) inorder(n->left, visit, cb_data);
    visit(n, cb_data);
    if (n->right) inorder(n->right, visit, cb_data);
}

void
postorder(Node *n, VisitCallback *visit, void *cb_data)
{
    if (n->left) postorder(n->left, visit, cb_data);
    if (n->right) postorder(n->right, visit, cb_data);
    visit(n, cb_data);
}

set<Node *>
find_all_ancestors(Node *node, map<Node *, Node *> parents)
{
    set<Node *> ancestors;
    for (Node *n = parents[node]; n; n = parents[n])
        ancestors.insert(n);
    return ancestors;
}

map<Node *, Node *> 
calc_parent_map(Node *root)
{
    map<Node *, Node *> parents;
    inorder(root, store_parents, &parents);
    return parents;
}

void
store_parents(Node *node, void *cb_data)
{
    map<Node *, Node *> *parents = (map<Node *, Node *> *)cb_data;
    if (node->left) (*parents)[node->left] = node;
    if (node->right) (*parents)[node->right] = node;
}

void
print_node(Node *node, void *cb_data)
{
    (void *)cb_data;
    cout << node->value << ' ';
}

Node *
lowest_common_ancestor(Node *n1, Node *n2, Node *root)
{
    map<Node *, Node *> parent = calc_parent_map(root);
    set<Node *> ancestors = find_all_ancestors(n1, parent);
    Node *n;
    for (n = n2; n != root; n = parent[n])
        if (find(ancestors.begin(), ancestors.end(), n) != ancestors.end())
            break;
    return n;
}

int
main(void)
{
    Node *n1 = new Node(1);
    Node *n2 = new Node(2);
    Node *n3 = new Node(3);
    Node *n4 = new Node(4);
    Node *n5 = new Node(5);
    Node *n6 = new Node(6);
    Node *n7 = new Node(7);
    Node *n8 = new Node(8);
    Node *n9 = new Node(9);
    Node *n10 = new Node(10);
    Node *n11 = new Node(11);
    Node *n12 = new Node(12);
    Node *n13 = new Node(13);
    Node *n14 = new Node(14);
    Node *n15 = new Node(15);

    n1->left = n2;
    n2->left = n3;
    n3->left = n4;
    n3->right = n5;
    n2->right = n6;
    n6->left = n7;
    n6->right = n8;
    n1->right = n9;
    n9->left = n10;
    n10->left = n11;
    n10->right = n12;
    n9->right = n13;
    n13->left = n14;
    n13->right = n15;

    cout << "preorder" << ' ';
    preorder(n1, print_node, NULL);
    cout << endl;
    cout << "inorder" << ' ';
    inorder(n1, print_node, NULL);
    cout << endl;
    cout << "postorder" << ' ';
    postorder(n1, print_node, NULL);
    cout << endl;

    Node *lca = lowest_common_ancestor(n5, n7, n1);
    cout << "lowest common ancestor: " << lca->value << endl;

    return 0;
}