Btree traversal

Posted on |

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)
	}
}