Data Structures: Find the Minimum and Maximum Height of a Binary Search Tree

Hey guys,

I am solving this challenge Data Structures: Find the Minimum and Maximum Height of a Binary Search Tree
Here’s my code

var displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
function BinarySearchTree() {
    this.root = null;
    // change code below this line
    // change code above this line
    this.findMinHeight = function(root = this.root) {
        // empty tree.
        if(root === null) {
            return -1;
        }
        // leaf node.
        if(root.left === null && root.right === null) {
            return 0;
        }
        if(root.left === null){
            return this.findMinHeight(root.right) + 1;
        }
        if(root.right === null){
            return this.findMinHeight(root.left) + 1;
        }
        const lHeight = this.findMinHeight(root.left);
        const rHeight = this.findMinHeight(root.right);
        return Math.min(lHeight, rHeight) + 1;
    };
    this.findMaxHeight = function(root = this.root) {
        // empty tree.
        if(root === null) {
            return -1;
        }
        // leaf node.
        if(root.left === null && root.right === null) {
            return 0;
        }
        if(root.left === null){
            return this.findMaxHeight(root.right) + 1;
        }
        if(root.right === null){
            return this.findMaxHeight(root.left) + 1;
        }
        const lHeight = this.findMaxHeight(root.left);
        const rHeight = this.findMaxHeight(root.right);
        return Math.max(lHeight, rHeight) + 1;
    };
    this.isBalanced = function(root = this.root) {
        
        if(root === null) {
            return true;
        }

        if(root.left === null && root.right === null){
            return true;
        }

        if(root.left === null) {
            return this.findMaxHeight(root.right) <= 0; 
        }

        if(root.right === null) {
             return this.findMaxHeight(root.left) <= 0; 
        }

        const lHeight = this.findMaxHeight(root.left);
        const rHeight = this.findMaxHeight(root.right);
        if(Math.abs(lHeight - rHeight) > 1){
            return false;
        }
        return this.isBalanced(root.left) && this.isBalanced(root.right);
    };
}

Everything is going find except isBalanced function. I am pretty much sure the logic I have written is correct. But I don’t know why test suit is failing. When I printed the root using displayTree function this the tree I have got.

{
  "value": 4,
  "left": {
    "value": 1,
    "left": null,
    "right": null
  },
  "right": {
    "value": 7,
    "left": null,
    "right": {
      "value": 87,
      "left": {
        "value": 34,
        "left": {
          "value": 8,
          "left": null,
          "right": null
        },
        "right": {
          "value": 45,
          "left": null,
          "right": {
            "value": 73,
            "left": null,
            "right": null
          }
        }
      },
      "right": null
    }
  }
}

To me, it looks like this tree is not balanced. So function should return false and it does so. But I don’t know why when I run the test suits, it says

// running test
The isBalanced method returns true if the tree is a balanced binary search tree.
// tests completed`

Can anyone please help me with this? Thanks.

Your code seems ok although there are redundancies.

I’ve used my code for this challenge. However, it didn’t pass the last case. This only tells me that the last testcase is incorrect. We definitely know the given tree is unbalanced because the left and right subtree height are 1 and 5. However, the testcase still demands true.

So, I’d suggest clean up your code and move on.

Testcode that I used: https://repl.it/@RoyGunhooGunhoo/BinarySearchTree-FCC

I’ll clean up my code and move to next. Thank you for helping me with this.

were u able to solve the isBalanced method.

Is there any particular place where we should be informing this kind of issues?
I know my code works, but as you said before, there is something wrong with the tests, and it is still not fixed.

test seems broken yeah. But i passes if you just return true without any conditions lol

Hi hk-skit,

Would you mind if we use your solution as the solution for this challenge? It is a valid solution, we are working on fixing the last test case which is incorrect.

for anyone still interested, i looked at the ‘tests’ on the github page and found that the last line is:

return !test.isBalanced();

being that ‘!’ negates the return value, i just changed all my return values to the opposite. for example, if the code is

if (this.root == null) return true

change it to:

if (this.root == null) return false

after that it passed fine. silly, but at least i got the green check mark!