Clever Geek Handbook

How do I calculate the depth of each node in a binary search tree?

My task is to calculate the depth of each node and store it at the depth specified in the node class. But I don't know how I should approach this problem. I have searched for some example on the internet but did not find one suitable for my task. This is the code for my given node class:

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

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

+3


source to share


2 answers 


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
    }
}


Calling with updateDepth(root, 0);

+3


source


Most binary tree algorithms work by recursion - you check a base condition to see if the recursion should stop, and then you do your thing for the left and right children, perhaps 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 it addDepth

's part of your class Node

):



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 case, I check the base condition right before the recursion, not (as in the first version) right before looking at the node.

+2


source






More articles:


All Articles