title: Explain why this binary tree traversal algorithm has O(NlogN) time complexity?
body: <p>I'm going through the Cracking the Coding Interview book right now and I'm doing a binary tree exercise. There is a snippet of code that is according to the book <code>O(NlogN)</code>, however, I don't understand why that is. I can understand if the algorithm was <code>O(N)</code>, but I don't know where the <code>logN</code> is coming from in their analysis.</p>
  
  <pre><code>int getHeight(TreeNode root) {
      if (root == null) return -1; // Base case
      return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
  }
  
  boolean isBalanced(TreeNode root) {
      if (root == null) return true; // Base case
  
      int heightDiff = getHeight(root.left) - getHeight(root.right);
      if (Math.abs(heightDiff) &gt; 1) {
          return false;
      } else { 
          // Recurse
          return isBalanced(root.left) &amp;&amp; isBalanced(root.right);
      }
  }
  </code></pre>