CODEWITHSUNDEEP
javadata-structuresbinary-treebinary-search-treetestcase
SomeoneLearning17
SomeoneLearning17

Reputation: 163

Height of a binary tree: why is this solution not passing 2/6 test cases in hackerrank?

Wrote a recursive solution for the height of a binary search tree that uses in-order traversal.

Every time the function reaches a "null" node (the end of a line), it resets the variable called "numLevels". Every time the method reaches the end of a line, if numLevels > finalVar, then finalVar becomes numLevels.

This is my solution:

 static int finalVar= 0;
    static int numLevels= 0; 
    
    public static int height(Node root) {
        // traverse (in order), ml++ with every recursive call, reset when node == null
        findHeight(root);
        
        if (finalVar-1 == 1) return 0;  // special case defined in instructions
        else{
              return finalVar-1;
        }
    }
    
    public static void findHeight(Node node){
        numLevels++;       // every time we recursive call, we add
        
        if (node == null){
            if (numLevels > finalVar){
                finalVar=numLevels;
            }
            numLevels=0;
            return;
        }
        findHeight(node.left);
        findHeight(node.right);
    }

and these are the two test cases that it isn't passing: test case 1

and: enter image description here

all the other test cases are passing. Can anyone spot the reason it's not working? :( thanks!

Upvotes: 1

Views: 203

Answers (1)

yeeshue99
yeeshue99

Reputation: 248

Just spitballing, but wouldn't setting numLevels to 0 also reset it for the other branch? Because remember that your recursive call goes all the way down the furthest left branch, then the branch to the right of the last left. numLevels at that time is 0, which would never be bigger than the other branch.

Since you're making a helper function anyways, there is no reason to have static variables. Just pass along the current max, and the count, and then do everything the same. That way, your current depth is "thread safe" in respect to your recursive depth.

Upvotes: 3

Related Questions