Fast deterministic backtrack search

The backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root, subject to the constraint that the children of a node are revealed only after their parent is visited. This note describes a fast, deterministic backtrack search algorithm for a p-processor COMMON CRCW-PRAM that visits any n-node tree of height h in time O ((n/p + h)(log log log p)^2). This upper bound compares favorably with a natural Omega(n/p + h) lower bound for this problem. Our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them