1

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.

bof
  • 78,265
learningboy
  • 71
  • 6
    I'm confused... in a tree, there is only ONE path between any two specified nodes. – Nick Peterson Dec 03 '16 at 19:20
  • 2
    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 03 '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 03 '16 at 19:29
  • @NickPeterson how did you derive $(n-2)!$ for the number of paths between two nodes for a complete graph? E.g. why isn't it $\sum_{k=1}^{n}n\text{P}k$ where $n\text{P}k$ is the $k$-permutations of $n$? (which according to these answers doesn't have a closed-form solution) – Josh Apr 26 '20 at 21:50

1 Answers1

0

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.

AlgorithmsX
  • 4,560