CODEWITHSUNDEEP
javabinary-search-treetreenode
Gregg
Gregg

Reputation: 125

How to calculate depth of each node in Binary Search Tree?

My task is to calculate depth of each node and store it in 'depth' given in Node class. But I don't know how I should approach this task. I was looking for some example in the internet but haven't found any appropriate to my task. This is the code of my given Node class:

Node
{int value; Node left, right; int depth;}

I thought I could use a similar method to counting height of a tree but it didn't work out. Any help?

Upvotes: 3

Views: 20572

Answers (2)

tucuxi
tucuxi

Reputation: 17935

Most algorithms on binary trees work by recursion - you check a base condition to see if recursion should stop, and then you do your thing for the left and right children, possibly accumulating what you find. In this case,

static void addDepth(Node n, int currentDepth) {
    if (n == null) return; // check base condition

    // store current depth in this node
    n.setDepth(currentDepth);

    // recursion
    addDepth(left, currentDepth+1);
    addDepth(right, currentDepth+1);
}

Or, alternatively (assuming that addDepth is part of your Node class):

void addDepth(int current) {
     depth = current;
     if (left != null) left.addDepth(current+1);
     if (right != null) right.addDepth(current+1);
}

Both versions are equivalent. In the second, I am checking the base condition right before recursion, instead of (as is done in the 1st version) right before looking at the node.

Upvotes: 3

Zereges
Zereges

Reputation: 5209

void updateDepth(Node node, int depth)
{
    if (node != null)
    {
        node.depth = depth;
        updateDepth(node.left, depth + 1); // left sub-tree
        updateDepth(node.right, depth + 1); // right sub-tree
    }
}

Call with updateDepth(root, 0);

Upvotes: 5

Related Questions