Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
For example, consider the following Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
Following are different input keys and their ancestors in the above tree
Input Key List of Ancestors ------------------------- 1 2 1 3 1 4 2 1 5 2 1 6 3 1 7 3 1 8 4 2 1 9 5 2 1 10 7 3 1
Recursive solution for this problem is discussed here.
It 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.
How 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.
Following is C implementation of the above approach.
C Programming:
[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”/]Output:
Following are all keys and their ancestors 1: 2: 1 3: 1 4: 2 1 5: 2 1 6: 3 1 7: 3 1 8: 4 2 1 9: 5 2 1 10: 7 3 1