{"id":111771,"date":"2025-11-06T07:00:00","date_gmt":"2025-11-06T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=111771"},"modified":"2025-11-06T09:29:17","modified_gmt":"2025-11-06T17:29:17","slug":"20251106-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20251106-00\/?p=111771","title":{"rendered":"Non-recursively deleting a binary tree in constant space: Synthesizing the parent pointer"},"content":{"rendered":"

Last time, we looked at a way to delete a binary tree non-recursively, assuming that we had parent pointers<\/a>. But nodes in a classical binary tree does not remember their parents, so we’ll have to use some other trick. Recursion is the traditional mechanism for remembering the parent of the node under study, but our goal here is to do it without recursion.<\/p>\n

The trick is to realize that each child pointer in the binary tree is traversed only once. Therefore, once you have traversed the pointer, it is superfluous and can be reused. Since the left child is traversed first, we can repurpose it to be the parent pointer.<\/p>\n

struct Node\r\n{\r\n    Node* left;\r\n    Node* right;\r\n    Data d;\r\n};\r\n\r\nvoid DeleteTree(Node* node)\r\n{\r\n    Node* parent = nullptr;\r\n    while (node) {\r\n        \/\/ Go left as far as you can.\r\n        while (node->left) {\r\n            \/\/ Move down and remember the old parent in the \"left\" pointer.<\/span>\r\n            node = std::exchange(node->left, std::exchange(parent, node)); <\/span>\r\n        }\r\n\r\n        \/\/ Remember the parent in the \"left\" pointer.<\/span>\r\n        node->left = parent;                         <\/span>\r\n\r\n        \/\/ If you can't go left, try going right one step,\r\n        \/\/ and then continue the leftward descent.\r\n        if (node->right) {\r\n            parent = node;<\/span>\r\n            node = node->right;\r\n            continue;\r\n        }\r\n\r\n        \/\/ At the bottom. Delete the node and head back up.\r\n        while (node) {\r\n            delete node;\r\n            if (!parent) {\r\n                return; \/\/ all done\r\n            }\r\n            \/\/ If we came from the left child,\r\n            \/\/ then go to the right child if there is one.\r\n            if (?????????????????????????????????????) {<\/span>\r\n                node = parent->right;                   <\/span>\r\n                break;\r\n            } else {\r\n                \/\/ No more children, so keep walking up.\r\n                node = parent;\r\n                parent = node->left;<\/span>\r\n            }\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
We solved the problem of keeping track of where the parent node is, but we created a new one: When we move up the tree, how do we know whether we came up from the left child or up from the right child?<\/p>\n
Well, we know that the right child is undamaged, so instead of saying “If we are not the left child, then we are the right child”, we can test the other child: “If we are not the right child, then we are the left child.”<\/p>\n
    if (node != parent->right && parent->right)\r\n<\/pre>\n
 Commenter Sebastian Redl noted that comparing pointers to deleted objects is undefined behavior<\/a>, so we’ll have to tweak the code.<\/p>\n
        \/\/ At the bottom. Delete the node and head back up.\r\n        while (node) {\r\n            bool from_left = node != parent->right;<\/span>\r\n            delete node;\r\n            if (!parent) {\r\n                return; \/\/ all done\r\n            }\r\n            \/\/ If we came from the left child,\r\n            \/\/ then go to the right child if there is one.\r\n            if (from_left<\/span> && parent->right) {\r\n                node = parent->right;\r\n                break;\r\n            } else {\r\n                \/\/ No more children, so keep walking up.\r\n                node = parent;\r\n                parent = node->left;\r\n            }\r\n        }\r\n\r\n<\/pre>\n
This code is tricky to write because you have to keep track of the point at which the left<\/code> changes to parent<\/code> for each node in the tree.<\/p>\n
 The solution on the Code Golf Stack Exchange<\/a> is a little different: It uses the right<\/code> pointer to record the “child node to process next”, so it is the original right<\/code> when the code traverses into the left child, and it turns to null<\/code> when the code traverses into the right child. The details are different but the basic idea is the same.<\/p>\n
As I noted last time, this was not the algorithm I came up with when I was presented with this challenge. We’ll look at that algorithm next time. (Spoiler alert: I like my algorithm better.)<\/p>\n","protected":false},"excerpt":{"rendered":"
Making one as you go.<\/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-111771","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Making one as you go.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111771","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=111771"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111771\/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=111771"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=111771"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=111771"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}