CODEWITHSUNDEEP
algorithmtreebinary-treebinary-search-tree
mntruell
mntruell

Reputation: 181

Number Of Ways To Traverse a Binary Tree

Consider a binary tree of n nodes. For the sake of example consider the following tree:

     1
   /   \
  2     3
 / \   / \
4   5 6   7
           \
            8

How many different ways can I fully traverse the tree starting from the root (top) node and only moving to un-visited nodes that are directly connected to ones that have already been visited (i.e. I can go from 1 to 2 to 4 but then to 3)?

Upvotes: 4

Views: 1437

Answers (2)

user206428
user206428

Reputation:

Programmatic verification of @deinst's answer, with Prolog: 

traverse([], []) :- !.
traverse(F, [N|P]) :-
    % select a frontier node from F
    select(t(N,C), F, Rem),
    % append all new accessible children to the frontier
    append(C, Rem, NewF),
    % traverse the remaining set
    traverse(NewF, P).

tree(X) :-
    X = t(1,[t(2,[t(4,[]), t(5,[])]),t(3,[t(6,[]), t(7,[t(8,[])])])]).

do :-
    tree(X),
    findall(P, (traverse([X], P), write_ln(P)), Ps),
    length(Ps, L),
    write_ln(L).

This does indeed return 210 possibilities, as suggested for your example tree.

?- do.
[1,2,4,5,3,6,7,8]
[1,2,4,5,3,7,8,6]
[1,2,4,5,3,7,6,8]
[1,2,4,3,6,7,8,5]
[1,2,4,3,6,7,5,8]
[1,2,4,3,6,5,7,8]
[1,2,4,3,7,8,6,5]
[1,2,4,3,7,8,5,6]
[1,2,4,3,7,6,8,5]
...
[1,3,2,7,6,4,8,5]
[1,3,2,7,6,4,5,8]
[1,3,2,7,6,5,8,4]
[1,3,2,7,6,5,4,8]
210
true.

Upvotes: 1

deinst
deinst

Reputation: 18782

You might have more luck asking on the Math Stack exchange.

You are asking for the number of linear extensions of the binary tree considered as a poset. Although I can see no general formula, one can solve this recursively as follows:

Find the number of ways of traversing the left and right subtrees (the empty tree is trivially traversed in 1 way). Call these T_L and T_R. Let #L and #R be the cardinality (size) of the left tree and right tree respectively. Then the number of ways of traversing the whole tree is

T_L * T_R * (#L + #R choose #L)

because we can traverse the left tree in T_L ways, the right tree in T_R ways (independent of how we traverse the right tree), and we can interleave the left and right trees in (#L + #R choose #L) ways.

In your example there are two ways of traversing the left tree, and three ways of traversing the right tree and (7 choose 3) is 35, so there are 2*3*35 = 210 ways of traversing the tree.

Upvotes: 5

Related Questions