CODEWITHSUNDEEP
javaalgorithm
cris
cris

Reputation: 275

Trying to find the diameter of a binary tree, but I don't know why I'm failing one particular test case

Was practicing my algorithms skills on leetcode, when I came across this question https://leetcode.com/problems/diameter-of-binary-tree/

I tried implementing something similar to finding the max depth of a tree. That's why I created a second function and called it with the left and right child nodes of the root node. But it doesn't 100% work and I can't figure it out. I pasted the test case that it fails.

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        return check(root.left) + check(root.right);
    }
    
    public int check(TreeNode root){
        if(root == null) return 0;
        
        return Math.max(check(root.left), check(root.right)) + 1;
    }
}

[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

The output is 7, but it needs to return 8. I pasted the link to the leetcode question so you can input the testcase and visualize the tree. I actually don't understand why it should equal 8. From my understanding the answer SHOULD be 7, but it needs to be 8 apparently. I posted it in the discussions part of the question but no ones responded.

Upvotes: 0

Views: 43

Answers (1)

Luke Woodward
Luke Woodward

Reputation: 64959

Your approach to calculating the diameter is wrong. It assumes that the longest path between any nodes goes through the root. Note that the question warns you against making this very assumption:

This path may or may not pass through the root.

Your code finds the path [7, 4, -3, -9, 9, 6, 0, -1], of length 7, but there is a longer path if you avoid the root node, [-1, 0, 6, 9, -9, -7, -6, 9, 2], and this has length 8. In this path, we head from leaf node -1 up four levels to -9 and then back down another four layers to leaf node 2 via the -6 on the right of -7.

Upvotes: 2

Related Questions