You don't need the axiom of choice for the countable case, which is all that's required for computer science.
Why is the AC necessary for this recursive tree traversal?
The AC is necessary[1] because at each of the infinitely many steps, you have to choose which of possibly several candidates to use.
[1] As mrmyers points out, you actually only need a weaker version of AC, called Countable Choice.
Theorem ("Konig's Lemma"): If a tree has infinitely many nodes, and every node has only finitely many children, then the tree must have an infinite branch.
Proof: The tree's root, X1, has infinitely many descendants. Since the root has only finitely many children, some child, X2, of the root, must have infinitely many descendants. Since X2 has only finitely many children, some child, X3, of X2, must have infinitely many descendants. This process repeats forever, producing a sequence X1, X2, X3, ... which is an infinite branch through the tree.