Monday, February 3, 2014

Minimum distance between the two nodes of tree

Given a binary tree(not BST) and two nodes in the tree(not necessarily leaf nodes), find the minimum distance between them.

Approach:

The minimum distance can be computed by first finding the LCA of the two nodes, and then finding the heights of the all the three nodes(2 nodes + 1 LCA) from the root. 
(For finding the LCA in the binary tree refer to the previous post
and finding the height of the element in the binary tree is self explanatory.)




Then the total distance can be computed as
 height(root, p) + height(root, q) - 2 * height (root, r) + 1;

int lca(struct tree * root, struct tree * p, struct tree * q, struct tree  *& res) {
    if(root == NULL || res != NULL)
        return 0;
    int found = 0;
    if(root == p || root == q)
        found = 1;
    found += lca(root->left, p, q, res);
    found += lca(root->right, p, q, res);
    if(res == NULL && found == 2)
        res = root;
    return found;
}

int height(struct tree * root, struct tree * p) {
    if (root == NULL)
        return -1;
    if(root == p)
        return 0;
    int r = max(height(root->left, p), height(root->right, p));
    return r >= 0 ? r + 1 : r;    
}

int minDist(struct tree * root, struct tree * p, struct tree * q) {
    struct tree * r = NULL;
    lca(root, p, q, r);
    if(r == NULL)
        return -1;
    cout<< r->data << endl;
    return height(root, p) + height(root, q) - 2 * height (root, r) + 1;
}

 

No comments :

Post a Comment