Error in p04_check_balanced.py

[PBearson]

Referring to this solution.

I think the current solution may be incorrect. Consider the following tree, which is unbalanced:

I can implement this tree and test if it is balanced with the following code. I just added it to the bottom of the example() function.

tree = BinaryNode(1)
tree.left = BinaryNode(2)
tree.right = BinaryNode(9)
tree.right.left = BinaryNode(10)
tree.left.left = BinaryNode(3)
tree.left.right = BinaryNode(7)
tree.left.right.right = BinaryNode(5)
tree.left.left.left = BinaryNode(6)
tree.left.right.left = BinaryNode(12)
tree.left.right.left.left = BinaryNode(16)
tree.left.right.left.right = BinaryNode(0)
print(is_balanced(tree)) # Should return False

However, this returns True.

[brycedrennan]

I agree. Do you want to submit a pull request to fix the test and provide a solution?

[smvazirizade]

I also confirm that the current solution is not correct. For example if you use the following Tree the code return True while this tree is not balanced.

    root.left = BinaryNode(2)
    root.left.left = BinaryNode(4)
    root.right = BinaryNode(3)
    root.right.left = BinaryNode(8)
    root.right.right = BinaryNode(9)
    root.right.right.right = BinaryNode(10)
    print(is_balanced(root))

[PBearson]

I submitted 2 solutions at #204 . If only one is preferred, I can remove the other one and update the PR.

[smvazirizade]

I submitted 2 solutions at #204 . If only one is preferred, I can remove the other one and update the PR.

Thank you Bryan. I read your solution and that was very slick indeed. I think that would be great if we can keep both of them in the repo.

[PBearson]

I submitted 2 solutions at #204 . If only one is preferred, I can remove the other one and update the PR.

Thank you Bryan. I read your solution and that was very slick indeed. I think that would be great if we can keep both of them in the repo.

Sounds good, Sayyed. I noticed that the first solution had a bug, so I fixed it. I also improved the space complexity of the second solution.

[brycedrennan]

Fixed in #204