{"id":111774,"date":"2025-11-07T07:00:00","date_gmt":"2025-11-07T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=111774"},"modified":"2025-11-07T08:54:12","modified_gmt":"2025-11-07T16:54:12","slug":"20251107-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20251107-00\/?p=111774","title":{"rendered":"Non-recursively deleting a binary tree in constant space: Restructuring the tree"},"content":{"rendered":"

We’ve been looking at non-recursive algorithms for deleting the nodes of a binary tree. The previous algorithm performed a postorder traversal<\/a>, cleverly repurposing the left<\/code> link as a parent<\/code> link once the left child pointer is no longer needed.<\/p>\n

As I noted at the start of the discussion, the algorithm I came up with was quite different.<\/p>\n

For ease of diagramming, let’s draw the binary tree rotated counter-clockwise 45 degrees, so that the root node in the northwest corner, with left nodes going down the page and right nodes going to the right. I focused on the two pieces coming from the root node: The long left (down) chain and as the right child.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n
A<\/td>\n\u2192<\/td>\n\ud83c\udf33<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
B<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
C<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
\u22ee<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
Z<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Before I can delete the root node, I have to arrange for the left and subtrees to be cleaned up eventually. My strategy is first to take the right subtree and graft it onto the end of the leftmost chain:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
A<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
B<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
C<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
\u22ee<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
Z<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
\ud83c\udf33<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

At this point, the root node has only one child, namely the left child. So I can delete the root node and treat the left child as the new root of what remains.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
A<\/td>\n\ud83d\udd25<\/td>\n<\/tr>\n
 <\/td>\n<\/tr>\n
B<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
C<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
\u22ee<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
Z<\/td>\n\u2192<\/td>\n\u2026<\/td>\n<\/tr>\n
\u2193<\/td>\n<\/tr>\n
\ud83c\udf33<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

I have now reduced the problem to a smaller problem: The new tree rooted at B has one fewer node than the one I started with, so I can repeat the process until all the nodes are deleted.<\/p>\n

void DeleteTree(Node* node)\r\n{\r\n    \/\/ Empty tree: Nothing to do\r\n    if (!node) return;\r\n\r\n    \/\/ Find the leftmost node.\r\n    Node* last = node;\r\n    while (last->left) {\r\n        last = last->left;\r\n    }\r\n\r\n    while (node)\r\n    {\r\n        \/\/ Make the right subtree the left subtree\r\n        \/\/ of the leftmost node.\r\n        last->left = node->right;\r\n\r\n        \/\/ Find the new leftmost node.\r\n        while (last->left) {\r\n            last = last->left;\r\n        }\r\n\r\n        \/\/ We have arranged for the eventual\r\n        \/\/ deletion of all the children. Now we can\r\n        \/\/ delete the root node and promote the left\r\n        \/\/ child to be the new root.\r\n        delete std::exchange(node, node->left);\r\n    }\r\n}\r\n<\/pre>\n
I like this algorithm because it is shorter and much easier to get correct. The order of element destruction is preorder-ish: Every parent is destroyed before its children, and every left child is destroyed before its right sibling. However, the right subtree is not destroyed immediately after the left subtree, so it’s not a true preorder. You can think of it as a topological order.<\/p>\n
The running time of this algorithm is O<\/var>(n<\/var>) because each node is deleted once, each right link is traversed once (to graft it to the bottom), and each left link is traversed twice (once to find the leftmost node and once when it becomes the root element and is detached from the rest of the tree prior to being deleted).<\/p>\n
Bonus chatter<\/b>: Note that the right thing happens if the root has no right child: A null tree gets grafted to the end of the leftmost node (which has no effect).<\/p>\n","protected":false},"excerpt":{"rendered":"
Changing the tree structure to make it easier to delete.<\/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-111774","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Changing the tree structure to make it easier to delete.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111774","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=111774"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111774\/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=111774"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=111774"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=111774"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}