http://www.geeksforgeeks.org/print-ancestors-of-a-given-binary-tree-node-without-recursion/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
void
printancestor(node *root,
int
key) {
19
if
(!root)
return
;
20
stack<node*>
S;
21
while
(
1
) {
22
while
(root && root->data !=
key) {
23
S.push(root);
24
root = root->
left;
25
}
26
if
(root && root->data == key)
break
;
27
if
(S.top()->right ==
NULL) {
28
root =
S.top();
29
S.pop();
30
while
(!S.empty() && S.top()->right ==
root) {
31
root =
S.top();
32
S.pop();
33
}
34
}
35
root = S.empty()? NULL : S.top()->
right;
36
}
37
while
(!
S.empty()) {
38
cout << S.top()->data <<
"
"
;
39
S.pop();
40
}
41
}
42
43
int
main() {
44
node *root =
new
node(
1
);
45
root->left =
new
node(
2
);
46
root->right =
new
node(
3
);
47
root->left->left =
new
node(
4
);
48
root->left->right =
new
node(
5
);
49
root->right->left =
new
node(
6
);
50
root->right->right =
new
node(
7
);
51
root->left->left->left =
new
node(
8
);
52
root->left->right->right =
new
node(
9
);
53
root->right->right->left =
new
node(
10
);
54
for
(
int
i =
1
; i <
11
; i++
) {
55
printancestor(root, i);
56
cout <<
endl;
57
}
58
return
0
;
59
}
Data Structure Binary Tree: Print ancestors of a given binary tree node without recursion
