# Total number of paths between any two nodes - Graph vs. Complete Binary Tree

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.

• I'm confused... in a tree, there is only ONE path between any two specified nodes. – Nick Peterson Dec 3 '16 at 19:20
• 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. – Nick Peterson Dec 3 '16 at 19:22
• @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. – 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.