CODEWITHSUNDEEP
binary-treedepth
ueg1990
ueg1990

Reputation: 1033

Sum of depth of all nodes in binary tree (Path length)

I am trying to implement a function to calculate path length of a binary tree and i am not able to get the correct answer. Can you check what i am doing wrong? Here is my code below:

public int pathLength() {
    int sum = 0;
    int c = 1;
    pathLength(root, sum);
    return sum;
}

public int pathLength(Node n, int sum) {
    if(n.isRoot())
        sum+= 0;
    if(n.left == null && n.right == null)
        return;
    c++;
    if(n.left != null)
        sum += c;
    if (n.right != null)
        sum+=c;
    pathLength(n.left, sum);
    pathLength(n.right, sum); 

}

Upvotes: 0

Views: 6782

Answers (3)

aar306
aar306

Reputation: 19

Here is an easy approach Time : O(n) while the space will be O(h) where h is the height of the binary tree:

int sum(BinaryTree *node, int count){
    if(node == nullptr){
        return 0;
    }
    

    return count + sum(node->left, count+1)+sum(node->right, count+1);
}

int nodeDepths(BinaryTree *root) {
    int count=0;
    int ans=0;
    ans =sum(root, count);
  return ans;

    }

Upvotes: 0

Hazel Wang
Hazel Wang

Reputation: 111

Is it because of you set the initial value of c as 1 instead of 0? The children of root should be at level 2 with the depth 1.

Upvotes: 0

001
001

Reputation: 13533

There are a lot of things wrong with this code. It wouldn't even compile because a) In the 2nd function c is never declared (it is local in the first) and b) the 2nd function never returns a value.

But the biggest issue is the way you declare the 2nd function. "sum" is passed by value. That basically means a new copy of "sum" is created each time you call the function and is discarded when the function ends.

What you want to do is pass by reference. When doing this, the actual sum variable, not a copy, is passed to the function. So your code might look like this:

public void pathLength(Node n, int& sum) {
    //if(n.isRoot())     <- not sure what this is for
    //    sum+= 0;

    sum += 1;   // Increment for this node

    //if(n.left == null && n.right == null)
    //    return;      // This conditional is not needed with next 2 if statements

    //c++;    <- Don't know what c is for

    // Recursively call for child nodes
    if(n.left != null)
        pathLength(n.left, sum);
    if (n.right != null)
        pathLength(n.right, sum); 
}

Note that this counts all the nodes in the tree. I assume that's what you want. If you want to find the deepest node, that's different.

Upvotes: 1

Related Questions