Monday, January 10, 2011

Finding Diameter of a Binary Tree.

Diameter Of A Binary Tree:

[1] calculate shortest paths between all possible pairs of nodes in the tree.

[2] the path which is longest among all the shortest paths found in step [1] is the Diameter of Tree.



Sample Binary Tree.




Method 1 (Using Recursive functions.)





Table to be used for reference with the code.


Source code


#include <iostream>
#include <map>
using namespace std;


struct Node
{
    Node()
    {
        pLeft = NULL;
        pRight = NULL;
        cData = 0;
        iMaxLeftWeight = 0;
        iMaxRightWeight = 0;
        iMax = 0;
        iTotalWeight = 0;
    }

    Node *pLeft;
    Node *pRight;
    char cData;

    //max possbile length of left subtree
    int iMaxLeftWeight;

    //max possbile length of right subtree
    int iMaxRightWeight;

    //max possible length of path that can be obtained from
    //traversing either left or right subtree.
    int iMax;

    //iTotalWeight = iMaxLeftWeight + iMaxRightWeight;
    //used to determine center of whole tree.
    //node with max iTotalWeight will be center.
    int iTotalWeight;
};

//structure to store all Node::iTotalWeight of tree.
//MaxWeightNodes stores elements in desending order of iTotalWeight.
//So, its first element corresponds to center of tree.
//definition : MaxWeightNodes[INDEX] = DATA
//here INDEX = Node::iTotalWeight and DATA = pointer to Node itself.
multimap<int, Node*, greater<int> > MaxWeightNodes;

//instead of using map we can keep track of node with max
//iTotalWeight and afterwards this node can be considered as center



int GetMaxWeight(Node *pNode)
{
    if(pNode->pLeft)
        pNode->iMaxLeftWeight = 1 + GetMaxWeight(pNode->pLeft);

    if(pNode->pRight)
        pNode->iMaxRightWeight = 1 + GetMaxWeight(pNode->pRight);

    pNode->iTotalWeight = pNode->iMaxLeftWeight + pNode->iMaxRightWeight;

    MaxWeightNodes.insert(make_pair(pNode->iTotalWeight, pNode));

    pNode->iMax = max(pNode->iMaxLeftWeight, pNode->iMaxRightWeight);

    return pNode->iMax;
}


Node* Traverse(Node *pNode)
{
    Node *pTempNode = NULL;

    if( (pNode->iMaxLeftWeight == 0) && (pNode->iMaxRightWeight == 0) )
        return pNode;

    if(pNode->iMaxLeftWeight > pNode->iMaxRightWeight)
        pTempNode = pNode->pLeft;
    else
    if(pNode->iMaxLeftWeight < pNode->iMaxRightWeight)
        pTempNode = pNode->pRight;
    else
        pTempNode = pNode->pRight;
        //pTempNode = pNode->pLeft;(anything will do)

    return Traverse(pTempNode);
}


void FindEndPointsOfDiameter(Node *pNode, Node **ppLeftEndPoint, Node **ppRightEndPoint)
{
    if(pNode->pLeft)
        (*ppLeftEndPoint) = Traverse(pNode->pLeft);
    else
        (*ppLeftEndPoint) = pNode;

    if(pNode->pRight)
        (*ppRightEndPoint) = Traverse(pNode->pRight);
    else
        (*ppRightEndPoint) = pNode;

    return;
}

void main()
{
/**
Node *pRoot = NULL;

//fill the tree
//assign pRoot to root of tree
//now pRoot points to the root of tree.

//GetMaxWeight() function will traverse every node of tree and fill
//following members (iMaxLeftWeight iMaxRightWeight iTotalWeight iMax)
//of traversed nodes.
GetMaxWeight(pRoot);

//first element of map 'MaxWeightNodes' corresponds to center of tree.
Node *pCenter = MaxWeightNodes.begin()->second;

//finding length of diameter of tree
//diameter can be obtained from center of tree.
//diameter = iTotalWeight = (max length of left subtree + max length of Right subtree)
int iDiameterOfTree = pCenter->iTotalWeight;

//finding endpoints of diameter of tree
Node *pLeftEndPoint = NULL;
Node *pRightEndPoint = NULL;
FindEndPointsOfDiameter(pCenter, &pLeftEndPoint, &pRightEndPoint);

//in similar manner we can find diameter(and its endpoints) correspoding
//to other centers of tree. Other center can be found from map MaxWeightNodes
//by fetching starting elements having max iTotalWeight.
/**/


    Node a1, a2, a3, a4, a5, a6, a7, a8, a9;

    a1.pLeft = &a2;
    a1.pRight = &a3;
    a1.cData = 1;

    a2.pLeft = &a4;
    a2.pRight = &a5;
    a2.cData = 2;

    a3.pLeft = NULL;
    a3.pRight = NULL;
    a3.cData = 3;

    a4.pLeft = &a6;
    a4.pRight = &a7;
    a4.cData = 4;

    a5.pLeft = NULL;
    a5.pRight = &a8;
    a5.cData = 5;

    a6.pLeft = &a9;
    a6.pRight = NULL;
    a6.cData = 6;

    a7.pLeft = NULL;
    a7.pRight = NULL;
    a7.cData = 7;

    a8.pLeft = NULL;
    a8.pRight = NULL;
    a8.cData = 8;

    a9.pLeft = NULL;
    a9.pRight = NULL;
    a9.cData = 9;


    Node *pRoot = &a1;

    GetMaxWeight(pRoot);

    Node *pCenter = MaxWeightNodes.begin()->second;

    int iDiameterOfTree = pCenter->iTotalWeight;

    Node *pLeftEndPoint = NULL;
    Node *pRightEndPoint = NULL;
    FindEndPointsOfDiameter(pCenter, &pLeftEndPoint, &pRightEndPoint);

}