{"id":1012,"date":"2023-04-22T16:55:54","date_gmt":"2023-04-22T08:55:54","guid":{"rendered":"https:\/\/www.cgdev.net\/blog\/?p=1012"},"modified":"2023-05-03T20:41:55","modified_gmt":"2023-05-03T12:41:55","slug":"binary-tree-traversal-algorithm-without-recursion","status":"publish","type":"post","link":"https:\/\/www.cgdev.net\/blog\/1012.html","title":{"rendered":"Binary Tree Traversal Algorithm Without Recursion"},"content":{"rendered":"<h3>Pre-Order Traversal<\/h3>\n<p>Because the characteristic of preorder traversal is to access the root node first, and then access the left and right subtrees, so the root node must be pushed into the stack first, then the root node of the right subtree is pushed in the stack, and then the root node of the left subtree is pushed into the stack, and then you can pop the stack and access it recursively. The basic idea is to use the last-in-first-out feature of the stack.<\/p>\n<pre lang='a_c'>\r\nvoid PreOrder(Node* root)\r\n{\r\n    stack<Node*> stk;    \r\n    Node* p = NULL;\r\n    stk.push(root);\r\n    while (stk.size())\r\n    {\r\n        p = stk.top();\r\n        Visit(p);\r\n        stk.pop(); \r\n        if (p->right) stk.push(p->right);\r\n\r\n        if (p->left) stk.push(p->left);\r\n    }\r\n}\r\n<\/pre>\n<h3>In-Order Traversal<\/h3>\n<p>In the inorder traversal, we recursively traverse the left subtree, visit the root node, and then traverse the right subtree.<br \/>\nThe most common use case is binary search tree.<\/p>\n<pre lang='a_c'>\r\nvoid Inorder(struct Node* node)\r\n{\r\n    Inorder(node->left);\r\n    Visit(node);\r\n    Inorder(node->right);\r\n}\r\n<\/pre>\n<p>The algorithm above is easy but has no performance, now let&#8217;s consider traverse the tree without recursion in a single while.<br \/>\nThe idea is: we first push the root in a stack, then check the top of the stack to see if it does not have left child or<br \/>\nit&#8217;s subtree has been traversed, if so we visit and pop it from the stack, and then continue to analyze its right subtree.<\/p>\n<pre lang='a_c'>\r\nvoid InOrderIterative(Node* root)\r\n{\r\n    stack<Node*> stk;\r\n    stk.push(root);\r\n    Node* p = NULL;\r\n    while (stk.size())\r\n    {\r\n        if (!stk.top()->left || p)\r\n        {           \r\n            p = stk.top();\r\n            Visit(p);\r\n            stk.pop(); \r\n            if (p->right)\r\n            {\r\n                stk.push(p->right); \r\n                p = NULL;\r\n            }         \r\n        }\r\n        else\r\n        {\r\n            stk.push(stk.top()->left);          \r\n        }\r\n    }\r\n}\r\n<\/pre>\n<h3>Post-Order Traversal<\/h3>\n<p>For postorder traversal, we visit the entire left subtree, then the entire right subtree, and then the root node.<br \/>\nThis means that the root node should be pushed in stack first so it can be the last node we can visit in the stack.<\/p>\n<pre lang='a_c'>\r\nvoid PostOrderIterative(Node* root) \r\n{\r\n    stack<Node*> stk;\r\n    stk.push(root);\r\n    Node *p = NULL, *L = NULL, *R = NULL;\r\n    while (stk.size())\r\n    {\r\n        L = stk.top()->left;\r\n        R = stk.top()->right;\r\n        if (!L && !R || R && p == R || !R && p == L) \r\n        {\r\n            p = stk.top();\r\n            stk.pop();\r\n            Visit(p);\r\n        }\r\n        else\r\n        {\r\n            if (R) stk.push(R);\r\n\r\n            if (L) stk.push(L);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<h3>M-ary tree<\/h3>\n<p>The algorithm for a binary tree can be generalized into a m-ary tree (a tree where each node have no more than m children nodes).<br \/>\nThe postorder algorithm for m-ary tree is:<\/p>\n<pre>\r\n    Traverse the subtrees.\r\n    Visit the root node.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Pre-Order Traversal Because the characteristic of preorder traversal is to access the root node first, and then access the left and right subtrees, so the root node must be pushed into the stack first, then the root node of the right subtree is pushed in the stack, and then the root node of the left [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[39],"tags":[],"class_list":["post-1012","post","type-post","status-publish","format-standard","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/posts\/1012","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/comments?post=1012"}],"version-history":[{"count":0,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/posts\/1012\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/media?parent=1012"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/categories?post=1012"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/tags?post=1012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}