Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

2 votes

Are reversed reverse preorder traversals equivalent to a postorder traversal?

Nathaniels simple and elegant proof is the best way to formally convince yourself your conjectures are true. I want to add a more informal and visual explanation. The postorder traversal of a binary ...
user avatar
  • 27.2k
4 votes
Accepted

Are reversed reverse preorder traversals equivalent to a postorder traversal?

This can be proven by induction on trees. I give details on the conjecture 1 here. It is clearly true for the empty tree and for leaves; Suppose it is true for trees $l$ and $r$. Consider $t$ a node ...
user avatar
  • 7,154
2 votes

Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

I think there may be a mistake in your statement, unless you allow a walk to stay in the same vertex on a step, instead of crossing an edge (but that's not the usual definition of walk), or unless you ...
user avatar
  • 7,154
0 votes

When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?

Krystal’s algorithm for constructing minimum spanning trees first sorts an array of edges in increasing order of weight, so that edges with the smallest weight can be considered first for selection.
user avatar
0 votes

When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?

Is that something we can't accomplish with some other representation? Edge list and adjacency list represent the same thing so if you can do something with one, you can do it with the other. In the ...
user avatar

Top 50 recent answers are included