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

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

#1

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.


#2

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


#3

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


#4

were u able to solve the isBalanced method.


#5

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.