In a graph, the total number of paths between any two nodes, is given by $n!$. Proof is in this link

In a Complete Binary tree, the total number of paths from root to leaf is basically, the number of leaves, which is $2^{\log_2n - 1}$ and the time complexity of finding these is $O(n)$ since you would have to visit every node for doing so.

My question is, what is the time complexity of finding all paths between any two nodes in a complete binary tree ? Is it $2^n$ since from any node, you have two paths?

Cross posting from MathOverflow, as this is a more appropriate forum for the discussion in question.

  • 2
    $\begingroup$ I'm confused... in a tree, there is only ONE path between any two specified nodes. $\endgroup$ – Nick Peterson Dec 3 '16 at 19:20
  • 1
    $\begingroup$ And also, the claim about graphs is incorrect as stated. The number of paths between two nodes in a graph depends entirely on the structure of the graph -- it may be 0, it may be large. The largest it could ever be, however, is $(n-2)!$, in the complete graph. $\endgroup$ – Nick Peterson Dec 3 '16 at 19:22
  • $\begingroup$ @NickPeterson, your comment about the number of paths between two gives nodes, being (n-2)! is correct. I meant to say, the number of paths from any node to any other node is n!. Is that correct? About the tree, again, I mean the same thing. What is the total number of paths from root to any/(all) leaves? PS : Editing the question to remove ambiguity. $\endgroup$ – learningboy Dec 3 '16 at 19:29

From Wikipeida:

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.

I have no idea why you would want all paths between all nodes, but it would probably be bounded by at least $O(n^3)$, since you have $n(n-1)\approx O(n^2)$ different nodes to choose from, and most depth-first search algorithms run in $O(n)$ time.

In short: $O(n)$ for finding the singular path between two nodes and $O(n^3)$ for finding all paths between any two nodes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.