{"id":27552,"date":"2018-02-06T20:56:55","date_gmt":"2018-02-06T15:26:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27552"},"modified":"2018-02-06T20:56:55","modified_gmt":"2018-02-06T15:26:55","slug":"print-ancestors-given-binary-tree-node-without-recursion","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/print-ancestors-given-binary-tree-node-without-recursion\/","title":{"rendered":"Print ancestors of a given binary tree node without recursion"},"content":{"rendered":"

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.<\/span><\/p>\n

For example, consider the following Binary Tree<\/p>\n

            1\r\n        \/       \\\r\n       2         3\r\n     \/   \\     \/   \\\r\n    4     5    6    7 \r\n   \/       \\       \/\r\n  8         9     10<\/pre>\n
Following are different input keys and their ancestors in the above tree<\/p>\n
Input Key    List of Ancestors \r\n-------------------------\r\n 1            \r\n 2            1\r\n 3            1\r\n 4            2 1\r\n 5            2 1\r\n 6            3 1\r\n 7            3 1\r\n 8            4 2 1\r\n 9            5 2 1\r\n10            7 3 1\r\n<\/pre>\n
Recursive solution for this problem is discussed here.
\nIt is clear that we need to use a stack based iterative traversal of the Binary Tree. The idea is to have all ancestors in stack when we reach the node with given key. Once we reach the key, all we have to do is, print contents of stack.
\nHow to get all ancestors in stack when we reach the given node? We can traverse all nodes in Postorder way. If we take a closer look at the recursive postorder traversal, we can easily observe that, when recursive function is called for a node, the recursion call stack contains ancestors of the node. So idea is do iterative Postorder traversal and stop the traversal when we reach the desired node.<\/p>\n
Following is C implementation of the above approach.<\/p>\n
C Programming:<\/strong><\/p>\n[pastacode lang=”c” manual=”%2F%2F%20C%20program%20to%20print%20all%20ancestors%20of%20a%20given%20key%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F%2F%20Maximum%20stack%20size%0A%23define%20MAX_SIZE%20100%0A%20%0A%2F%2F%20Structure%20for%20a%20tree%20node%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20Node%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20Structure%20for%20Stack%0Astruct%20Stack%0A%7B%0A%20%20%20%20int%20size%3B%0A%20%20%20%20int%20top%3B%0A%20%20%20%20struct%20Node*%20*array%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20tree%20node%0Astruct%20Node*%20newNode(int%20data)%0A%7B%0A%20%20%20%20struct%20Node*%20node%20%3D%20(struct%20Node*)%20malloc(sizeof(struct%20Node))%3B%0A%20%20%20%20node-%3Edata%20%3D%20data%3B%0A%20%20%20%20node-%3Eleft%20%3D%20node-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20return%20node%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20stack%20of%20given%20size%0Astruct%20Stack*%20createStack(int%20size)%0A%7B%0A%20%20%20%20struct%20Stack*%20stack%20%3D%20(struct%20Stack*)%20malloc(sizeof(struct%20Stack))%3B%0A%20%20%20%20stack-%3Esize%20%3D%20size%3B%0A%20%20%20%20stack-%3Etop%20%3D%20-1%3B%0A%20%20%20%20stack-%3Earray%20%3D%20(struct%20Node**)%20malloc(stack-%3Esize%20*%20sizeof(struct%20Node*))%3B%0A%20%20%20%20return%20stack%3B%0A%7D%0A%20%0A%2F%2F%20BASIC%20OPERATIONS%20OF%20STACK%0Aint%20isFull(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20return%20((stack-%3Etop%20%2B%201)%20%3D%3D%20stack-%3Esize)%3B%0A%7D%0Aint%20isEmpty(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20return%20stack-%3Etop%20%3D%3D%20-1%3B%0A%7D%0Avoid%20push(struct%20Stack*%20stack%2C%20struct%20Node*%20node)%0A%7B%0A%20%20%20%20if%20(isFull(stack))%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20stack-%3Earray%5B%2B%2Bstack-%3Etop%5D%20%3D%20node%3B%0A%7D%0Astruct%20Node*%20pop(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20if%20(isEmpty(stack))%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%20%20%20return%20stack-%3Earray%5Bstack-%3Etop–%5D%3B%0A%7D%0Astruct%20Node*%20peek(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20if%20(isEmpty(stack))%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%20%20%20return%20stack-%3Earray%5Bstack-%3Etop%5D%3B%0A%7D%0A%20%0A%2F%2F%20Iterative%20Function%20to%20print%20all%20ancestors%20of%20a%20given%20key%0Avoid%20printAncestors(struct%20Node%20*root%2C%20int%20key)%0A%7B%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%20return%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20stack%20to%20hold%20ancestors%0A%20%20%20%20struct%20Stack*%20stack%20%3D%20createStack(MAX_SIZE)%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20complete%20tree%20in%20postorder%20way%20till%20we%20find%20the%20key%0A%20%20%20%20while%20(1)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20the%20left%20side.%20While%20traversing%2C%20push%20the%20nodes%20into%0A%20%20%20%20%20%20%20%20%2F%2F%20the%20stack%20so%20that%20their%20right%20subtrees%20can%20be%20traversed%20later%0A%20%20%20%20%20%20%20%20while%20(root%20%26%26%20root-%3Edata%20!%3D%20key)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20push(stack%2C%20root)%3B%20%20%20%2F%2F%20push%20current%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20root%20%3D%20root-%3Eleft%3B%20%20%2F%2F%20move%20to%20next%20node%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20node%20whose%20ancestors%20are%20to%20be%20printed%20is%20found%2C%0A%20%20%20%20%20%20%20%20%2F%2F%20then%20break%20the%20while%20loop.%0A%20%20%20%20%20%20%20%20if%20(root%20%26%26%20root-%3Edata%20%3D%3D%20key)%0A%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20right%20sub-tree%20exists%20for%20the%20node%20at%20top%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20not%20then%20pop%20that%20node%20because%20we%20don’t%20need%20this%0A%20%20%20%20%20%20%20%20%2F%2F%20node%20any%20more.%0A%20%20%20%20%20%20%20%20if%20(peek(stack)-%3Eright%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20root%20%3D%20pop(stack)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20popped%20node%20is%20right%20child%20of%20top%2C%20then%20remove%20the%20top%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20as%20well.%20Left%20child%20of%20the%20top%20must%20have%20processed%20before.%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Consider%20the%20following%20tree%20for%20example%20and%20key%20%3D%203.%20%20If%20we%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20remove%20the%20following%20loop%2C%20the%20program%20will%20go%20in%20an%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20infinite%20loop%20after%20reaching%205.%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%2F%20%20%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%202%20%20%20%20%203%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%204%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20%205%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(!isEmpty(stack)%20%26%26%20peek(stack)-%3Eright%20%3D%3D%20root)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20root%20%3D%20pop(stack)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20stack%20is%20not%20empty%20then%20simply%20set%20the%20root%20as%20right%20child%0A%20%20%20%20%20%20%20%20%2F%2F%20of%20top%20and%20start%20traversing%20right%20sub-tree.%0A%20%20%20%20%20%20%20%20root%20%3D%20isEmpty(stack)%3F%20NULL%3A%20peek(stack)-%3Eright%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20stack%20is%20not%20empty%2C%20print%20contents%20of%20stack%0A%20%20%20%20%2F%2F%20Here%20assumption%20is%20that%20the%20key%20is%20there%20in%20tree%0A%20%20%20%20while%20(!isEmpty(stack))%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20pop(stack)-%3Edata)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20construct%20a%20binary%20tree%0A%20%20%20%20struct%20Node*%20root%20%3D%20newNode(1)%3B%0A%20%20%20%20root-%3Eleft%20%3D%20newNode(2)%3B%0A%20%20%20%20root-%3Eright%20%3D%20newNode(3)%3B%0A%20%20%20%20root-%3Eleft-%3Eleft%20%3D%20newNode(4)%3B%0A%20%20%20%20root-%3Eleft-%3Eright%20%3D%20newNode(5)%3B%0A%20%20%20%20root-%3Eright-%3Eleft%20%3D%20newNode(6)%3B%0A%20%20%20%20root-%3Eright-%3Eright%20%3D%20newNode(7)%3B%0A%20%20%20%20root-%3Eleft-%3Eleft-%3Eleft%20%3D%20newNode(8)%3B%0A%20%20%20%20root-%3Eleft-%3Eright-%3Eright%20%3D%20newNode(9)%3B%0A%20%20%20%20root-%3Eright-%3Eright-%3Eleft%20%3D%20newNode(10)%3B%0A%20%0A%20%20%20%20printf(%22Following%20are%20all%20keys%20and%20their%20ancestors%5Cn%22)%3B%0A%20%20%20%20for%20(int%20key%20%3D%201%3B%20key%20%3C%3D%2010%3B%20key%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%3A%20%22%2C%20key)%3B%0A%20%20%20%20%20%20%20%20printAncestors(root%2C%20key)%3B%0A%20%20%20%20%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”\/]\n
Output:<\/strong><\/p>\n
Following are all keys and their ancestors\r\n1:\r\n2: 1\r\n3: 1\r\n4: 2 1\r\n5: 2 1\r\n6: 3 1\r\n7: 3 1\r\n8: 4 2 1\r\n9: 5 2 1\r\n10: 7 3 1<\/pre>\n","protected":false},"excerpt":{"rendered":"
Print ancestors of a given binary tree node without recursion – Stack – Given a Binary Tree and a key, write a function that prints all the ancestors<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[81755,81754,81751,81757,81752,81756,81753,81760,81758,81759],"class_list":["post-27552","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","tag-ancestor-in-tree-data-structure","tag-ancestor-node-definition","tag-ancestors-of-a-node-in-a-binary-tree","tag-check-if-all-leaves-are-at-same-level","tag-common-ancestor-of-two-nodes-in-a-binary-tree","tag-descendant-in-tree-data-structure","tag-find-parent-of-a-node-in-binary-tree","tag-find-parent-of-a-node-in-binary-tree-c","tag-find-parent-of-a-node-in-binary-tree-in-c","tag-print-ancestors-of-a-given-binary-tree-node-without-recursion"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27552","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27552"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27552\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}