Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The cost of traversing the tree is <strong><code>n-1</code></strong> where <code>n</code> is the number of nodes.</p> <p>This is true because every tree has exactly <code>n-1</code> edges - and you need to use all of them in order to visit all the nodes.</p> <hr> <p>To be exact it is known that the next 3 statements are equivalent for a <em>graph</em> <code>T</code> with <code>n</code> nodes:</p> <ol> <li>T is a tree (connected without cycles)</li> <li>T is connected and has n-1 edges</li> <li>T has no cycle and has n-1 edges</li> </ol> <p>From the above we can conclude, that in a tree, in order to get to all nodes we must use all edges (because there are no cycles, so no redundant edges) - and there are EXACTLY <code>n-1</code> of those.</p> <hr> <p><strong>EDIT</strong>:</p> <p>From your example it seems you are also counting the times you go back from each edge (i.e. some edges are counted twice).</p> <p>Well, in this case the optimal solution will be:</p> <pre><code>cost = (n-1)*2 - height </code></pre> <p><strong>Explanation/proof guidelines:</strong> <br>There are <code>n-1</code> edges exactly in the tree. Each of them is traversed exactly twice except those that leads from the root to the deepest node. <br>You must use each edge (except the mentioned) exactly twice, because with exception of the last branch - you go back from each node. <br>Since there are exactly <code>height</code> edges in the last branch, you get total of <code>cost = (n-1)*2 - height</code></p> <p>Note that it is basically the same as you got:</p> <pre><code>height + 2*(n-1-height) = height + 2(n-1) -2height = 2(n-1) - height </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POWhat is the minimum cost to traverse a binary Tree
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USamit
    1. USamit
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhat is the minimum cost to traverse a binary Tree
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 Awesome solution!
      singulars
      1. PO
      1. USChasefornone
    2. COPity OP hasn't upvoted or accepted....
      singulars
      1. PO
      1. USMitch Wheat
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload