Binary Tree

Recursive Traversial

Preorder Traversial

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorderTraversal(root, res);
return res;
}

void preorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) return;
res.push_back(root->val);
preorderTraversal(root->left, res);
preorderTraversal(root->right, res);
}

Inorder Traversial

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversal(root, res);
return res;
}

void inorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) return;
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}

Postorder Traversial

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorderTraversal(root, res);
return res;
}

void postorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) return;
postorderTraversal(root->left, res);
postorderTraversal(root->right, res);
res.push_back(root->val);
}

Iterative Traversial

Preorder Traversial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;

stack<TreeNode*> S;
TreeNode* p = root;
while (p != nullptr || !S.empty()) {
while (p != nullptr) {
cout << p-> val << endl;
res.push_back(p->val);
S.push(p);
p = p->left;
}

p = S.top(); S.pop();
p = p->right;
}

return res;
}

Inorder Traversial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;

stack<TreeNode*> S;
TreeNode* p = root;
while (p != nullptr || !S.empty()) {
while (p != nullptr) {
S.push(p);
p = p->left;
}

p = S.top(); S.pop();
res.push_back(p->val); // inorder
p = p->right;
}

return res;
}

Postorder Traversial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;

stack<TreeNode*> S;
S.push(root);
while (!S.empty()) {
TreeNode* p = S.top(); S.pop();
res.push_back(p->val);
if (p->left != nullptr) S.push(p->left);
if (p->right != nullptr) S.push(p->right);
}

reverse(res.begin(), res.end());
return res;
}

Level Order Traversial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> Q;
if (root == nullptr) return res;
Q.push(root);
while (!Q.empty()) {
int k = Q.size();
int j = res.size();
res.push_back(vector<int>());
for (int i = 0; i < k; i++) {
TreeNode* p = Q.front(); Q.pop();
res[j].push_back(p->val);
if (p->left != nullptr) Q.push(p->left);
if (p->right != nullptr) Q.push(p->right);
}
}

return res;
}