{"id":108726,"date":"2023-09-06T07:00:00","date_gmt":"2023-09-06T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108726"},"modified":"2023-09-05T14:31:22","modified_gmt":"2023-09-05T21:31:22","slug":"20230906-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230906-00\/?p=108726","title":{"rendered":"Detecting whether a tree-like data structure contains a cycle"},"content":{"rendered":"

Suppose you are given a tree-like data structure, in the sense that you are given a root node, and each node has children. You want to validate that the data structure indeed represents a tree, with no cycles.<\/p>\n

You can actually solve this problem by combining two things you already know how to do.<\/p>\n

First, you can walk the tree and generate elements. If the necessary node-traversal methods are available, You can use one of the iterative tree-walking algorithms<\/a>. Otherwise, you can use a traditional depth-first search with a stack. This converts the tree-like structure into a linear list.<\/p>\n

Next, you can use Floyd’s two-pointer algorithm for finding a cycle in a linked list. This will tell you whether your tree loops back on itself.<\/p>\n

Bingo, problem solved by combining two things you already know.<\/p>\n

Bonus chatter<\/b>: If you have to manage an explicit stack, then the memory usage can reach twice the number of nodes in the worst case. Alternatively, you can build a hash table of nodes that have been visited so far, and stop if you ever revisit a node before reaching the end of the tree. This caps the memory usage to the number of nodes.<\/p>\n

Bonus bonus chatter<\/b>: If you know the total number N<\/var> of nodes, say, say because it’s recorded in the file format, or you can count them while you load the file, then you don’t need to use Floyd’s two-pointer cycle-finding algorithm. You can just walk through the tree until you either (1)\u00a0reach the end, or (2)\u00a0have walked through N<\/var> nodes. Because once you reach node N<\/var> + 1, you know that you must have revisited a node due to the pigeonhole principle, and therefore found a cycle.<\/p>\n","protected":false},"excerpt":{"rendered":"

Combining two things we already know.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-108726","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

Combining two things we already know.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108726","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=108726"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108726\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=108726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=108726"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=108726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}