Here's a way to do this in O(n) time and O(1) space. It requires mutating the alleged tree, but can restore it to its original state before returning.
Level 1
Starting at the root, find the end of the right-linked-list, asserting that it does not contain a cycle. Then, right-link the end node to itself.
This is the trick that makes it work. The end node right-linked to itself effectively marks all the preceding nodes as "visited" in a reversible way that is still recognizable as the end of a right-linked-list.
Level n
Process the nodes in level n-1, and for each node that has a left child:
- Find the end of the child's right-linked-list, asserting that it does not contain a cycle. Note that if the node is previously visited, the assertion will fail, because the right-linked-list will end in a single-node cycle.
- Right-link the end node to itself.
- If the current right child is not the first right child, then right-link the previous child's right-end-node to the current child. The right-linked-lists for all of the left children will thereby by linked into a single list that ends in a single-node cycle. The start points of the original sublists are remembered by the left pointers in level (n-1), so the original lists are easily recoverable.
When you process a level that has no left-children, you've completed the tree and discovered that it is valid. If the cycle-free assertion fails at any point, then it is not a tree.
Recovery
Whether the alleged tree was valid or not, you can then restore it to its original state by processing level-by level, breaking up the appended left-child lists and nulling out the self-links at the end of every right-linked-list. Stop at the first invalid left-child you found, if any.
In order to do this in O(1) space, you need to process the levels in bottom-up order. To make that possible, traverse the path from the root to the last level start, and use the left-link each successor back to its predecessor. Then you can start at the last level and follow the left-links up.
In order to fix up the left links after you follow them back/up, you need to know whether they invert a right link or a (now overwritten) left link from the target. Just compare the current node to the target's (preserved) right link in order to distinguish these cases.
Here's an implementation in Typescript.
interface Node {
left?: Node,
right?: Node;
}
function checkTree(root: Node): boolean {
if (!root) {
return true;
}
// LEVEL 1
if (!validateRightList(root)) {
return false;
}
let levelStart = root;
// LEVEL N
// We'll set this to a left child if the tree is invalid
let invalidNode: Node | undefined;
let next = findLeftLink(levelStart);
while (next) {
let levelEnd = validateRightList(next.left!);
if (!levelEnd) {
invalidNode = next.left;
break;
}
levelStart = next.left!;
while (next.right !== next && (next = findLeftLink(next.right))) {
const s = next.left!;
const e = validateRightList(s);
if (!e) {
invalidNode = s;
break;
}
// concatenate next level lists
levelEnd.right = s;
levelEnd = e;
}
next = invalidNode ? undefined : findLeftLink(levelStart);
}
// Validation complete. PREPARE FOR RECOVERY
let prev: Node | undefined = undefined;
for (let n = root; n !== levelStart;) {
next = n.left ? n.left : n.right!;
n.left = prev; // note root.left == undefined now
prev = n;
n = next;
}
// remember the last overwritten left link in the recovery backtracking list
let savedLeft = levelStart.left;
levelStart.left = prev;
// RECOVERY
recoverRightList(levelStart);
while (levelStart.left) {
let nextLevel: Node | undefined = levelStart;
// move up to prev level
next = levelStart.left; // node with left link in prev level
recoverRightList(next);
levelStart.left = savedLeft; // fixed
savedLeft = levelStart;
levelStart = next;
while (levelStart && levelStart.left && levelStart.left.right === levelStart) {
// recover right link
levelStart = levelStart.left;
levelStart.right!.left = savedLeft;
savedLeft = undefined;
}
// split up the level we just left
next = findLeftLink(next.right);
while (nextLevel && next) {
const n: Node | undefined = nextLevel.right;
if (n == next.left) {
nextLevel.right = undefined;
next = findLeftLink(next.right);
}
nextLevel = n;
}
}
levelStart.left = savedLeft;
// all done
return !invalidNode;
}
/**
* Find the end of the right-linked-list and link it to itself
* @returns the end node, or undefined if there is a cycle
*/
function validateRightList(n: Node): Node | undefined {
let slow = n;
while (n.right?.right) {
n = n.right.right;
slow = slow.right!;
if (slow == n) {
return undefined; // found a cycle
}
}
if (n.right) {
n = n.right;
}
n.right = n;
return n;
}
/**
* Undo validateRightList and return end
*/
function recoverRightList(n: Node): Node {
while (n.right && n.right !== n) {
n = n.right;
}
n.right = undefined;
return n;
}
/**
* Traverse a terminated or validated right-list to find
* a node with a left child
*/
function findLeftLink(n: Node | undefined): Node | undefined {
if (!n) {
return undefined;
}
while (!n.left && n.right && n.right !== n) {
n = n.right!;
}
return n.left ? n : undefined;
}
Here is a test that checks the pictured example:
function treeToString(root: Node) : string {
const map = new Map<Node, number>();
const list: string[] = [];
function f(n: Node | undefined) {
if (!n) {
return;
}
if (map.has(n)) {
list.push(String(map.get(n)));
return;
}
map.set(n, map.size);
list.push('(');
f(n.left);
list.push(',');
f(n.right);
list.push(')');
}
f(root);
return list.join('');
}
const testTree = {
right: {
left: {
left: {},
right: {}
},
right: {
left: {
left: {},
right: {}
},
right: {}
}
}
} as Node;
console.log(`test Tree: ${treeToString(testTree)}`);
console.log(`valid: ${checkTree(testTree)}`);
console.log(`recovered: ${treeToString(testTree)}`);
testTree.right!.right!.left!.right = testTree.right!.left;
console.log(`test Tree: ${treeToString(testTree)}`);
console.log(`valid: ${checkTree(testTree)}`);
console.log(`recovered: ${treeToString(testTree)}`);
bool containsCycle(Tree t) { return false; }. Trees cannot contain cycles by definition. Did you mean to ask if any general graph contains a cycle?