title: How to efficiently check whether it's height balanced for a massively skewed binary search tree?
body: <p>I was reading <a href="https://stackoverflow.com/a/2178292/2180879">this answer</a> on how to check if a BST is height balanced, and really hooked by the bonus question:</p>
  
  <blockquote>
    <p>Suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?</p>
  </blockquote>
  
  <p>What would be a good strategy here?</p>
  
  <p>I am thinking to do a level order traversal and track the depth, if a leaf is found and current node depth is bigger than the leaf node depth + 2, then it's not balanced. But how to combine this with height checking?</p>
  
  <p>Edit: below is the implementation in the linked answer</p>
  
  <pre><code>IsHeightBalanced(tree)
      return (tree is empty) or 
             (IsHeightBalanced(tree.left) and
             IsHeightBalanced(tree.right) and
             abs(Height(tree.left) - Height(tree.right)) &lt;= 1)
  </code></pre>