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

Question

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?

Like everything in a search tree, you should approach it recursively. Draw a tree on a piece of paper and traverse it using a pen, writing down all the node depths as you go. Once that's done, try to put into words how you did it. With any luck, an algorithm will be clear from there. — biziclop
– biziclop, Commented Jun 11, 2015 at 10:09
See geeksforgeeks.org/get-level-of-a-node-in-a-binary-tree or tekmarathon.com/2013/05/02/find-depth-of-binary-search-tree. — Mihai8
– Mihai8, Commented Jun 11, 2015 at 10:10

Zereges · Accepted Answer · 2015-06-11 10:20:37Z

5

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);

answered Jun 11, 2015 at 10:20

Zereges

5,2191 gold badge31 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

tucuxi · Accepted Answer · 2015-06-11 10:20:45Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related