{"id":10024,"date":"2022-09-27T10:27:06","date_gmt":"2022-09-27T10:27:06","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10024"},"modified":"2022-10-10T09:23:45","modified_gmt":"2022-10-10T09:23:45","slug":"iterative-method-to-find-ancestors-of-a-given-binary-tree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/","title":{"rendered":"Iterative Method to find Ancestors of a Given Binary Tree"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg\" alt=\"\" \/><\/p>\n<h3>Problem Statement:<\/h3>\n<p>Given a Binary Tree, you need to find all the ancestors of a particular node of that binary tree. You will be given the value that is stored in a particular node.<\/p>\n<p>Constraint: You cannot use recursion.<\/p>\n<h3>Example:<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183102104-1-01.png\" alt=\"\" \/><\/p>\n<p>As shown in the image above, we have the key 80 and the ancestors of 80 are 10,20, and 50. So, we have printed a list containing the ancestors of the given key node.<\/p>\n<h3>Approach<\/h3>\n<p>The idea is to use the iterative postorder traversal. While traversing the tree in postorder iteratively, we stop the traversal when we find the key value and we will have the ancestors of the key already in the stack that we used for iterative postorder traversal. So, we will print the elements of the stack.<\/p>\n<p>Now, we just need to recall how to traverse the tree in postorder iteratively.<\/p>\n<h3>Iterative Postorder Traversal<\/h3>\n<p>We know that the postorder traversal is \u201cleft-right root\u201d. This means that we have to try to go to the left of the given tree till it is possible. Then, we have to traverse the right of the tree till it is possible. After traversing both left and right, we have to print. So, the algorithm that we are going to use depends highly on our attempts to maintain the \u201cleft-right root\u201d order.<\/p>\n<p>Let us see what the algorithm is.<\/p>\n<h3>Algorithm:<\/h3>\n<ul>\n<li>Assign a variable current to the root of the tree and initialize a stack of nodes (initially empty).<\/li>\n<li>While current does not become null OR the stack is not empty\n<ul>\n<li>If the current is not equal to null\n<ul>\n<li>Push current into the stack.<\/li>\n<li>Move current to its left.<\/li>\n<\/ul>\n<\/li>\n<li>Else\n<ul>\n<li>Assign a variable temp to the right child at the top of the stack.<\/li>\n<li>So, the top of the stack might or might not have the right child. So, if the temp is null\n<ul>\n<li>temp = stack.top()<\/li>\n<li>stack.pop()<\/li>\n<li>Add temp to the postorder<\/li>\n<li>While the stack is not empty AND the temp variable is equal to the right child of the top of the stack,\n<ul>\n<li>temp = stack.top()<\/li>\n<li>stack.pop()<\/li>\n<li>Add temp to the postorder<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<li>Else, current  = temp.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>So, this algorithm helps maintain the postorder i.e. \u201cleft-right root\u201d. Let us see an example dry run for the above algorithm.<\/p>\n<h3>Dry Run<\/h3>\n<p>Consider the following tree shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183134839-1-02.png\" alt=\"\" \/><\/p>\n<p>So, we will start by having the variable curr (current) at the root of the tree.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183154565-1-03.png\" alt=\"\" \/><\/p>\n<p>So, according to the first step of the algorithm, since current is not equal to null, we add it to the stack and move it to its left.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183165070-1-04.png\" alt=\"\" \/><\/p>\n<p>We keep on repeating this step as shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183175589-1-05.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183186335-1-06.png\" alt=\"\" \/><\/p>\n<p>So, the value of current is now null as after pushing 30 into the stack, it moved to its left child which is null. Now, we follow the else condition in the algorithm. So, we will take a variable temp that will be the right child at the top of the stack. Since the top of the stack is 30, temp = right child of 30 i.e. 40.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183203062-1-07.png\" alt=\"\" \/><\/p>\n<p>Since a temp is not equal to null, current will now move to temp.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183213394-1-08.png\" alt=\"\" \/><\/p>\n<p>Since the current is now not null, we add it to the stack and move to its left child.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183224940-1-09.png\" alt=\"\" \/><\/p>\n<p>So, we see that again, the steps will be repeated. This means that every time, we try to go to the left child of every node and if the left is null, we move to its right. This will keep happening till we reach Node 60.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183240116-1-10.png\" alt=\"\" \/><\/p>\n<p>Now, the temp will be the right of the top of the stack. This means the temp will be the right of 60. So, temp = null.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183255518-1-11.png\" alt=\"\" \/><\/p>\n<p>Since temp = null, we pop a value from the stack and it becomes temp and we also add it to the postorder.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183272024-1-12.png\" alt=\"\" \/><\/p>\n<p>Now, while the stack is not empty AND temp is equal to the right child of the top of the stack, we have to keep popping from the stack and adding the node to the post order.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183286573-1-13.png\" alt=\"\" \/><\/p>\n<p>So, 50 was popped and added to the postorder. Now, we will pop 40 since the right child of 40 is equal to temp.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183301492-1-14.png\" alt=\"\" \/><\/p>\n<p>This will continue as shown below.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183314058-1-15.png\" alt=\"\" \/><\/p>\n<p>Now the right child of the top of the stack is null but temp = 30 (Node 30 not value). So, again, we see that curr = null and we follow the above-discussed steps.<br \/>\nYou can complete the rest of the traversal yourself and you will find that we end up having the postorder of the tree correctly.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183328997-1-16.png\" alt=\"\" \/><\/p>\n<p>So, now that we have understood the procedure, let us write the code for the same.<\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_10025 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_10025 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_10025 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_10025 .wpsm_nav-tabs > li.active > a, #tab_container_10025 .wpsm_nav-tabs > li.active > a:hover, #tab_container_10025 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_10025 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_10025 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_10025 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_10025 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_10025 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_10025 .wpsm_nav-tabs > li > a:hover , #tab_container_10025 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_10025 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_10025 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_10025 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_10025 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_10025 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_10025 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_10025 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_10025 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_10025 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_10025 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_10025 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_10025\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_10025\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_10025_1\" aria-controls=\"tabs_desc_10025_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_10025_2\" aria-controls=\"tabs_desc_10025_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_10025\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_10025_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include &lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n\r\nstruct Node {\r\n\tint data;\r\n\tstruct Node* left, *right;\r\n};\r\n\r\nstruct Node* newNode(int data)\r\n{\r\n\tstruct Node* node = (struct Node*)malloc(sizeof(struct Node));\r\n\tnode-&gt;data = data;\r\n\tnode-&gt;left = node-&gt;right = NULL;\r\n\treturn node;\r\n}\r\n\r\nvoid printAncestors(struct Node* root, int key)\r\n{\r\n\tif (root == NULL)\r\n\t\treturn;\r\n\r\n\tstack&lt;struct Node*&gt; st;\r\n\r\n\twhile (1) {\r\n\r\n\t\twhile (root &amp;&amp; root-&gt;data != key) {\r\n\t\t\tst.push(root); \r\n\t\t\troot = root-&gt;left; \r\n\t\t}\r\n\r\n\t\tif (root &amp;&amp; root-&gt;data == key)\r\n\t\t\tbreak;\r\n\r\n\t\tif (st.top()-&gt;right == NULL) {\r\n\t\t\troot = st.top();\r\n\t\t\tst.pop();\r\n\r\n\t\t\twhile (!st.empty() &amp;&amp; st.top()-&gt;right == root) {\r\n\t\t\t\troot = st.top();\r\n\t\t\t\tst.pop();\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\troot = st.empty() ? NULL : st.top()-&gt;right;\r\n\t}\r\n\r\n\twhile (!st.empty()) {\r\n\t\tcout &lt;&lt; st.top()-&gt;data &lt;&lt; &quot; &quot;;\r\n\t\tst.pop();\r\n\t}\r\n}\r\n\r\nint main()\r\n{\r\n\t\/\/ Let us construct a binary tree\r\n\tstruct Node* root = newNode(10);\r\n\troot-&gt;left = newNode(20);\r\n\troot-&gt;right = newNode(30);\r\n\troot-&gt;left-&gt;left = newNode(40);\r\n\troot-&gt;left-&gt;right = newNode(50);\r\n\troot-&gt;right-&gt;left = newNode(60);\r\n\troot-&gt;right-&gt;right = newNode(70);\r\n\troot-&gt;left-&gt;right-&gt;left = newNode(80);\r\n\troot-&gt;right-&gt;left-&gt;left = newNode(90);\r\n\r\n    \r\n\tint key = 80;\r\n\tprintAncestors(root, key);\r\n\r\n\treturn 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_10025_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nimport java.util.*;\r\n\r\nclass Main\r\n{\r\nstatic class Node\r\n{\r\n\tint data;\r\n\tNode left, right;\r\n}\r\n\r\nstatic Node newNode(int data)\r\n{\r\n\tNode node = new Node();\r\n\tnode.data = data;\r\n\tnode.left = null;\r\n\tnode.right = null;\r\n\treturn node;\r\n}\r\n\r\nstatic void printAncestors(Node root, int key)\r\n{\r\n\tif (root == null)\r\n\t\treturn;\r\n\r\n\tStack&lt;Node&gt; st = new Stack&lt;Node&gt; ();\r\n\r\n\twhile (1 == 1)\r\n\t{\r\n\r\n\t\twhile (root != null &amp;&amp; root.data != key)\r\n\t\t{\r\n\t\t\tst.push(root);\r\n\t\t\troot = root.left;\r\n\t\t}\r\n\r\n\t\tif (root != null &amp;&amp; root.data == key)\r\n\t\t\tbreak;\r\n\r\n\t\tif (st.peek().right == null)\r\n\t\t{\r\n\t\t\troot = st.peek();\r\n\t\t\tst.pop();\r\n\r\n\t\t\twhile (!st.isEmpty() &amp;&amp; st.peek().right == root)\r\n\t\t\t{\r\n\t\t\t\troot = st.peek();\r\n\t\t\t\tst.pop();\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\troot = st.isEmpty() ? null : st.peek().right;\r\n\t}\r\n\r\n\twhile (!st.isEmpty())\r\n\t{\r\n\t\tSystem.out.print(st.peek().data + &quot; &quot;);\r\n\t\tst.pop();\r\n\t}\r\n}\r\n\r\npublic static void main(String[] args)\r\n{\r\n\tNode root = newNode(10);\r\n\troot.left = newNode(20);\r\n\troot.right = newNode(30);\r\n\troot.left.left = newNode(40);\r\n\troot.left.right = newNode(50);\r\n\troot.right.left = newNode(60);\r\n\troot.right.right = newNode(70);\r\n\troot.left.right.left = newNode(80);\r\n\troot.right.left.right = newNode(90);\r\n\r\n\tint key = 80;\r\n\tprintAncestors(root, key);\r\n}\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_10025 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_10025 a\"),jQuery(\"#tab-content_10025\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Time Complexity:<\/strong> The time complexity of the above algorithm is O(N) as we might have to traverse the entire tree in the worst case.<\/p>\n<p><strong>Space Complexity (Auxiliary Space):<\/strong> The auxiliary space is O(N) as we have used a stack to traverse in post order iteratively.<\/p>\n<p>We tried to discuss Iterative Method to find Ancestors of a Given Binary Tree. We hope this article gives you a better understanding of Iterative Method to find Ancestors of a Given Binary Tree, <a href=\"https:\/\/www.prepbytes.com\/\" title=\"PrepBytes\">PrepBytes<\/a> also provides a good collection of <a href=\"https:\/\/www.prepbytes.com\/prepbytes-courses\" title=\"Foundation Courses\">Foundation Courses<\/a> that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our <a href=\"https:\/\/www.prepbytes.com\/placement-preparation-program\" title=\"Placement Program\">Placement Program<\/a> which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Statement: Given a Binary Tree, you need to find all the ancestors of a particular node of that binary tree. You will be given the value that is stored in a particular node. Constraint: You cannot use recursion. Example: As shown in the image above, we have the key 80 and the ancestors of [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-10024","post","type-post","status-publish","format-standard","hentry","category-miscellaneous"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Iterative Postorder Traversal | Set 2 (Using One Stack) | PrepBytes Blog<\/title>\n<meta name=\"description\" content=\"In this article, we will be discussing Iterative Postorder Traversal, Also we have discussed a simple Iterative Postorder Traversal using two stacks in the previous post.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Iterative Postorder Traversal | Set 2 (Using One Stack) | PrepBytes Blog\" \/>\n<meta property=\"og:description\" content=\"In this article, we will be discussing Iterative Postorder Traversal, Also we have discussed a simple Iterative Postorder Traversal using two stacks in the previous post.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2022-09-27T10:27:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-10-10T09:23:45+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Iterative Method to find Ancestors of a Given Binary Tree\",\"datePublished\":\"2022-09-27T10:27:06+00:00\",\"dateModified\":\"2022-10-10T09:23:45+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\"},\"wordCount\":917,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg\",\"articleSection\":[\"Miscellaneous\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\",\"name\":\"Iterative Postorder Traversal | Set 2 (Using One Stack) | PrepBytes Blog\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg\",\"datePublished\":\"2022-09-27T10:27:06+00:00\",\"dateModified\":\"2022-10-10T09:23:45+00:00\",\"description\":\"In this article, we will be discussing Iterative Postorder Traversal, Also we have discussed a simple Iterative Postorder Traversal using two stacks in the previous post.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Miscellaneous\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/miscellaneous\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Iterative Method to find Ancestors of a Given Binary Tree\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Iterative Postorder Traversal | Set 2 (Using One Stack) | PrepBytes Blog","description":"In this article, we will be discussing Iterative Postorder Traversal, Also we have discussed a simple Iterative Postorder Traversal using two stacks in the previous post.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/","og_locale":"en_US","og_type":"article","og_title":"Iterative Postorder Traversal | Set 2 (Using One Stack) | PrepBytes Blog","og_description":"In this article, we will be discussing Iterative Postorder Traversal, Also we have discussed a simple Iterative Postorder Traversal using two stacks in the previous post.","og_url":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2022-09-27T10:27:06+00:00","article_modified_time":"2022-10-10T09:23:45+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Iterative Method to find Ancestors of a Given Binary Tree","datePublished":"2022-09-27T10:27:06+00:00","dateModified":"2022-10-10T09:23:45+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/"},"wordCount":917,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg","articleSection":["Miscellaneous"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/","url":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/","name":"Iterative Postorder Traversal | Set 2 (Using One Stack) | PrepBytes Blog","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg","datePublished":"2022-09-27T10:27:06+00:00","dateModified":"2022-10-10T09:23:45+00:00","description":"In this article, we will be discussing Iterative Postorder Traversal, Also we have discussed a simple Iterative Postorder Traversal using two stacks in the previous post.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1664183341628-Topic.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/iterative-method-to-find-ancestors-of-a-given-binary-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Miscellaneous","item":"https:\/\/prepbytes.com\/blog\/category\/miscellaneous\/"},{"@type":"ListItem","position":3,"name":"Iterative Method to find Ancestors of a Given Binary Tree"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/10024","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=10024"}],"version-history":[{"count":1,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/10024\/revisions"}],"predecessor-version":[{"id":10026,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/10024\/revisions\/10026"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=10024"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=10024"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=10024"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}