-
Notifications
You must be signed in to change notification settings - Fork 7
/
CS_44_BoundaryOrderTraversal.cpp
150 lines (130 loc) · 3.2 KB
/
CS_44_BoundaryOrderTraversal.cpp
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class TreeNode
{
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T data)
{
this->data = data;
left = NULL;
right = NULL;
}
~TreeNode()
{
if (left)
delete left;
if (right)
delete right;
}
};
void getLeftBoundary(TreeNode<int> *root, vector<int> &ans)
{
// if root is a leaf node then return as we don't need to add leaf node in the
// left boundary
if (root->left == NULL && root->right == NULL)
{
return;
}
// push the data of the current node
ans.push_back(root->data);
// if left child is not NULL then move to the left child
if (root->left != NULL)
{
getLeftBoundary(root->left, ans);
}
// if left child is NULL then move to the right child
else
{
getLeftBoundary(root->right, ans);
}
}
void getRightBoundary(TreeNode<int> *root, vector<int> &ans)
{
// if root is a leaf node then return as we don't need to add leaf node in the
// right boundary
if (root->left == NULL && root->right == NULL)
{
return;
}
// if right child is not NULL then move to the right child
if (root->right != NULL)
{
getRightBoundary(root->right, ans);
}
// if right child is NULL then move to the left child
else
{
getRightBoundary(root->left, ans);
}
// push the data of the current node when the recursive stack unwinds
// resulting in the right boundary from bottom to top
ans.push_back(root->data);
}
void getLeaves(TreeNode<int> *root, vector<int> &ans)
{
// base case
if (root == NULL)
{
return;
}
// if root is a leaf node then push the data of the current node
if (root->left == NULL && root->right == NULL)
{
ans.push_back(root->data);
}
// move to the left child and right child recursively to find the leaf nodes
getLeaves(root->left, ans);
getLeaves(root->right, ans);
}
vector<int> traverseBoundary(TreeNode<int> *root)
{
// ans will store the boundary order traversal
vector<int> ans;
// push the root node
ans.push_back(root->data);
// get the left boundary
if (root->left != NULL)
{
getLeftBoundary(root->left, ans);
}
// get the leaves
getLeaves(root, ans);
// get the right boundary
if (root->right != NULL)
{
getRightBoundary(root->right, ans);
}
return ans;
}
// hardcoded main function
int main()
{
// considering tree as
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// /
// 7
TreeNode<int> *root = new TreeNode<int>(1);
root->left = new TreeNode<int>(2);
root->left->right = new TreeNode<int>(5);
root->left->right->left = new TreeNode<int>(7);
root->right = new TreeNode<int>(3);
root->right->right = new TreeNode<int>(6);
root->left->left = new TreeNode<int>(4);
vector<int> ans = traverseBoundary(root);
cout << "Boundary order traversal of the tree is : ";
for (auto i : ans)
{
cout << i << " ";
}
cout << endl;
delete root;
return 0;
}