Btree traversal

Btree traversal is obvious to implement in recursion. here are non-recursion implementation, which needs std::stack or std::queue data structure to store the next level nodes in both deep-first-search idea and breadth-first-search idea, link. these are good examples of using stack, queue.

usage in leetCode114, flatten a BTree to a linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
void preorder_print(TreeNode* leaf)
{
if(leaf == nullptr)
return;
std::stack<int> s;
TreeNode* tmp ;
s.clear(); //
s.push(leaf);
while(!s.empty())
{
tmp = s.pop();
cout << tmp->value << ', ' ;
if(leaf->right != nullptr)
s.push(leaf->right);
if(leaf->left != nullptr)
s.push(leaf->left);
}
}
void inorder_print(TreeNode* leaf)
{
std::stack<int> s ;
s.clear();
TreeNode *tmp;
while( !s.empty() || leaf!=nullptr)
{
if(leaf != nullptr)
{
s.push(leaf);
leaf = leaf->left;
}else
{
tmp = s.top();
s.pop();
cout << tmp->value << ', ' ;
leaf = leaf->right;
}
}
}
void postorder_print(TreeNode* leaf)
{
std::stack<int> s ;
s.clear();
TreeNode *lastNodeVisited = nullptr ;
TreeNode *peekNode = nullptr;
while( !s.empty() || leaf != nullptr)
{
if(leaf != nullptr)
{
s.push(leaf);
leaf = leaf->left;
}else
{
peekNode = s.top();
if(peekNode->right != nullptr && lastNodeVisited != peekNode->right)
leaf = peekNode->right;
else
{
cout << peekNode->value << ', ';
lastNodeVisited = s.top();
s.pop();
}
}
}
}
void bfs_print(TreeNode* leaf)
{
std::queue<int> q ;
q.clear();
q.push(leaf);
TreeNode *node;
while( ! q.empty())
{
node = q.front();
q.pop();
cout << node->vaue << ', ';
if(node->left != nullptr)
q.push(node->left);
if(node->right != nullptr)
q.push(node->right)
}
}