Let $T_n$ be the set of nodes on level $n$ of a complete binary tree of height $\omega$: $T_0$ is just the root, so it has $2^0=1$ node, $T_1$ has $2^1$ nodes, and in general $T_n$ has $2^n$ nodes. If the tree isn’t complete, the levels may be smaller, but the point is that they are all finite. Their union is the set of all nodes of the tree, and the union of countably many finite sets is countable.
Now suppose that each node has countably infinitely many children. Label the root of the tree with the empty sequence, $\langle\rangle$. Label the nodes on level $1$, the children of the root, with $1$-tuples of natural numbers: $\langle 0\rangle,\langle 1\rangle,\langle 2\rangle,\dots~$. Label their children with $2$-tuples; for instance, the first three children of $\langle1\rangle$ are $\langle 1,0\rangle,\langle1,1\rangle$, and $\langle1,2\rangle$. On level $4$ you’ll find nodes with labels like $\langle 3,0,5,3\rangle$: this node is the child of $\langle 3,0,5\rangle$, which is the child of $\langle 3,0\rangle$, the child of $\langle 3\rangle$, the child of $\langle\rangle$, the root. In this way you can assign every node in the tree a unique label that is a finite sequence of natural numbers, and every such finite sequence will be attached to a node of the tree. Thus, there are exactly as many nodes as there are labels.
There is only one empty label, and there are obviously $\aleph_0$ (countably infinitely many) labels on level $1$, one for each natural number. The labels on level $n$ are just the elements of the set $\Bbb N^n$, and it’s a basic fact of infinite cardinalities that $\Bbb N^n$ is countably infinite for each $n\in\Bbb Z^+$. Thus, each level of the tree has countably many nodes, and the union of countably many countable sets is still countable, so this tree also has only countably many nodes, not continuum-many.
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.
Best Answer
Assuming each level of the tree is countable, the set of infinite paths is always either countable or has cardinality $\mathfrak{c}$. To see this, let $T_n$ be the $n$th level of the tree. The set of branches can then be considered as a subset $B$ of the product $\prod_n T_n$. In fact, $B$ is a closed subset of $\prod_n T_n$ with respect to the product topology when you give each $T_n$ the discrete topology. Since each $T_n$ is countable by hypothesis, the space $\prod_n T_n$ is a Polish space, and so $B$ is a Polish space as well. In particular, this implies $B$ is either countable or has cardinality $\mathfrak{c}$ (as a consequence of the Cantor-Bendixson theorem).