title: Why does this code to check if a binary tree is balanced take time O(n log n) when it recomputes depths multiple times?
body: <p>This code is meant to check if a binary tree is balanced (balanced being defined as a tree such that the heights of the two subtrees of any node never differ by more than one.</p>
  
  <p>I understand the N part of the runtime O(NlogN). The N is because every node in the tree is visited at least once.</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>
  
  <p>What I don't understand is the logN part of the runtime O(NlogN). The code will trace every possible path from a node to the bottom of the tree. Therefore should the code be more like N2^N or something? How does one step by step come to the conclusion that the runtime is O(NlogN)?</p>