{"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=\u201dc\u201d manual=\u201d%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\u2013%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\u2019t%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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}]}}