[Math] Total number of paths between any two nodes – Graph vs. Complete Binary Tree

Question

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.

Answer 1

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.