title: Height of General Tree
body: <p>I am doing Data structures and Algorithms in C++ (2nd Edition) by Tamassia and Goodrich</p>
  
  <p>I could not understand the running time of height of General Tree T as O(n + sum_over_p(1 + dp)) where n is the number of nodes of T and dp is the depth of node p (Page no 276).</p>
  
  <p>The concept used here is "the height of tree is the maximum depth of external nodes"</p>
  
  <p>Here is the code for finding the height of tree as given in book</p>
  
  <pre><code>int height1(const Tree&amp; T) {
      int h = 0;
      PositionList nodes = T.positions(); // list of all nodes
      for (Iterator q = nodes.begin(); q != nodes.end(); ++q) { 
          if (q−&gt;isExternal())
              h = max(h, depth(T, *q)); // get max depth among leaves
      }
      return h;
  }
  </code></pre>
  
  <p>Thanks!!</p>
  
  <p><strong>Update</strong></p>
  
  <p>The code for depth function is </p>
  
  <pre><code>int depth(const Tree&amp; T, const Position&amp; p) {
      if (p.isRoot())
          return 0; // root has depth 0
      else
          return 1 + depth(T, p.parent()); // 1 + (depth of parent)
  }
  </code></pre>