13,095,658 members (52,235 online)
Rate this:
See more:
Hi,
I'm having a little trouble with creating a function to find the average depth of a binary search tree. The definition of average depth of a tree is the sum of the depth of all nodes divided by the total number of nodes. The definition of the depth of a node is the distance from the root of the tree to the node. Can anyone help me?

So an example would be if you had a BST of:

```     6
/   \
3     8
/ \     \
2   4     9
\
5
```

Then the average depth is 1.571 because from 6 to 3 has depth of 1 and 6 to 2 has depth of 2. Do that for the rest of the nodes and sum them up then divide by the total number of nodes and that is the average depth. So it's (1 + 1 + 2 + 2 + 2 + 3)/7. Can anyone help me?
Posted 23-Apr-11 14:24pm
Updated 23-Apr-11 14:44pm
v3

Rate this:

## Solution 1

The problem is not finding the depth, the problem is to do it just once. Here is the way to do it: do not create a function for finding a depth of the current node. Instead, include the depth of a current node as a parameter of the recursive function.

```void AccumulateNodeInfo(
node * parent, uint parentDepth,
uint & accumulatedDepth, uint & nodeCount);```

Initialize `accumulatedDepth` and `nodeCount` to 0 and call this function with the root node. The function should call the current node's children with `parentDepth + 1`, add `parentDepth` to `accumulatedDepth` and increment the `nodeCount`. After this function traverses all the tree, `accumulatedDepth` will be equal to sum of the depths and `nodeCount` equal to the node count.

—SA
algrn912005 24-Apr-11 16:53pm

Thank you, that worked beautifully.
SAKryukov 24-Apr-11 21:14pm

Great. You're welcome.
Thanks for accepting this solution.
Good luck,
--SA
Rate this:

## Solution 2

For every thing i do with trees i use walk functions.
Example for a walk function:
```class INode
{
public:
INode*  _child;
INode*  _next;
};

class IWalk
{
public: // IWalk
virtual HRESULT Enter(INode* pNode) = 0;
virtual HRESULT Leave(INode* pNode) = 0;
};

void Walk(INode* pNode,IWalk* pWalk)
{
if(pNode && pWalk)
{
if(S_OK==pWalk->Enter(pNode))
{
for(INode* p=pNode->_child;p;p=p->_next) Walk(p,pWalk);
pWalk->Leave(pNode);
}
}
}

//////////
// implementation
class iWalk : public IWalk
{
public: // IWalk
virtual HRESULT Enter(INode* pNode){ ++_node_count; _node_level_sum += _level; ++_level; return S_OK; }
virtual HRESULT Leave(INode* pNode){ --_level; return S_OK; }

iWalk(){ _node_count = _node_level_sum = _level = 0; }

unsigned int  _node_count;
unsigned int  _node_level_sum;
unsigned int  _level;
};

double Calc()
{
iWalk  w;
Walk(root,&w);
return 0<w._node_count?(double)w._node_level_sum/(double)w._node_count:0;
}
```

Good luck.
Rate this:

## Solution 3

You have to find average depth at once .I use this formula->
This you can find from the formula as we can find maximum no.of nodes by //n=(2^d)-1
Where d is depth of the tree.
v2

Top Experts
Last 24hrsThis month
 OriginalGriff 210 Karthik Bangalore 65 Graeme_Grant 65 Mohibur Rashid 59 RickZeeland 55
 OriginalGriff 4,131 Graeme_Grant 2,232 ProgramFOX 2,057 Jochen Arndt 1,735 ppolymorphe 1,735