How can I construct a recursive pattern guard?

Question

I am modelling binary trees in Wolfram Language by writing them as three-element lists, like so: binTree = {nodeVal, leftChild, rightChild}.

It does not yet matter what kind of structure nodeVal itself has, but let us assume, for the sake of this problem, that the structure is a list of two integers: nodeValPattern = {_Integer, _Integer}.

Furthermore, leftChild and rightChild can be either {} or have internal nodes of the same shape as binTree itself.

I would like to have a pattern guard for the structure of binTree. The naive attempt does not work:

nodeValPattern = {_Integer, _Integer};
binTreePattern = {nodeValPattern, ({} | binTreePattern), ({} | binTreePattern)};
binTree = {
    {{1, 2}, {{2, 3}, {}, {}}, {}},
    {{3, 4}, {}, {{4, 5}, {}, {}}},
    {}
};
MatchQ[binTree, binTreePattern]

I get the following error:

$RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>

Can you please help?

Answer 1

Your pattern has itself in its own definition. Mathematica will keep substituting the definition in at each level until it runs out of stack. From this answer about recursive string matching we can see a potential solution: using MatchQ instead of the explicit pattern, since Condition will prevent the recursive part of the pattern from being evaluated when it's defined.

Condition // Attributes
(* {HoldAll, Protected} *)

Thus we can try this:

binTreePattern2 = {nodeValPattern, ({} | (a_ /; 
     MatchQ[a, binTreePattern2])), ({} | (b_ /; 
     MatchQ[b, binTreePattern2]))};

MatchQ[binTree, binTreePattern2]
(* False *)

It turns out your tree is not correctly formed! (Look at binTree // TreeForm). Here is an example of a correctly formed tree.

binTree2 = {{10, 11}, {{1, 2}, {{2, 3}, {}, {}}, {}}, {{3, 
   4}, {}, {{4, 5}, {}, {}}}};

MatchQ[binTree2, binTreePattern2]
(* True *)

Answer 2

Referencing How to match expressions with a repeating pattern and How to define a recursive pattern? it is in my opinion superior to use a test function definition, which is easily made a pattern with _?test, to using Condition and MatchQ to avoid an infinite loop.

1. It more easily handles the case should one need to keep parts of the expression unevaluated during testing.

2. It appears to be more efficient in all cases that I have compared.

For this problem:

test[{{_Integer, _Integer}, {} | _?test, {} | _?test}] := True;
_test = False;

Or equivalently you can define the function with pattern sub-parts if you prefer, to improve clarity in large patterns:

node = {_Integer, _Integer};
leaf = {} | _?test;

test[{node, leaf, leaf}] := True
_test = False;

• In either case you could leave out _test = False if test will always be used in _?test but I prefer to make test a complete predicate function.

Now a large tree to your specification for the purpose of testing:

$RecursionLimit = 10000;
make[] := If[RandomInteger[] == 0, {}, {RandomInteger[9, 2], make[], make[]}];
SeedRandom[835];
bigTree = make[];

Size:

Depth[bigTree]
LeafCount[bigTree]

1642

877496

Speed compared to 2012rcampion's binTreePattern2:

MatchQ[bigTree, binTreePattern2] // RepeatedTiming
MatchQ[bigTree, _?test]          // RepeatedTiming

{0.1790, True}

{0.0764, True}