# Binary Tree Level Order Traversal in C/C++

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:

`    3    / /   9  20     /  /    15   7`
`3    / /   9  20     /  /    15   7`

should return its level order traversal as:

`[   [3],   [9,20],   [15,7] ]`
`[   [3],   [9,20],   [15,7] ]`

### Iterative DFS

DFS (Depth First Search) visits the nodes as deep as possible (front left to right nodes). If we record the current level, and should be able to push the node value to its corresponding level vector.

`/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<vector<int>> levelOrder(TreeNode* root) {         vector<vector<int>> r;         if (root == NULL) {             return r;         }         stack<pair<TreeNode*, int>> st;         auto p = root;         int level = 0;         while (p || !st.empty()) {             if (p) {                 if (level + 1 > r.size()) {                     r.resize(level + 1);                 }                 r[level].push_back(p->val);                 st.push(make_pair(p, level++));                 p = p->left;             } else {                 auto x = st.top();                 p = x.first;                 level = x.second + 1;                 st.pop();                 p = p->right;             }         }         return r;             } };`
`/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<vector<int>> levelOrder(TreeNode* root) {         vector<vector<int>> r;         if (root == NULL) {             return r;         }         stack<pair<TreeNode*, int>> st;         auto p = root;         int level = 0;         while (p || !st.empty()) {             if (p) {                 if (level + 1 > r.size()) {                     r.resize(level + 1);                 }                 r[level].push_back(p->val);                 st.push(make_pair(p, level++));                 p = p->left;             } else {                 auto x = st.top();                 p = x.first;                 level = x.second + 1;                 st.pop();                 p = p->right;             }         }         return r;             } };`

This emulate the recursion using the stack data structure. When new left nodes are pushed to the stack, the level is also recorded.

### Iterative BFS

Breadth First Search (BFS) implements a level-by-level traversal. We initialize the queue by the Root node and level 0, level-by-level pushing the nodes. When dealing a node, we push its value to its corresponding level vector.

`class Solution { public:     vector<vector<int>> levelOrderBottom(TreeNode* root) {         vector<vector<int>> r;         if (root == NULL) {             return r;         }         queue<pair<TreeNode*, int>> q;         q.push(make_pair(root, 0));         while (!q.empty()) {             auto p = q.front();             q.pop();             if (p.second >= r.size()) {                 r.push_back(vector<int>());             }             r[p.second].push_back(p.first->val);             if (p.first->left != NULL) {                 q.push(make_pair(p.first->left, p.second + 1));             }             if (p.first->right != NULL) {                 q.push(make_pair(p.first->right, p.second + 1));             }         }         return r;     } };`
`class Solution { public:     vector<vector<int>> levelOrderBottom(TreeNode* root) {         vector<vector<int>> r;         if (root == NULL) {             return r;         }         queue<pair<TreeNode*, int>> q;         q.push(make_pair(root, 0));         while (!q.empty()) {             auto p = q.front();             q.pop();             if (p.second >= r.size()) {                 r.push_back(vector<int>());             }             r[p.second].push_back(p.first->val);             if (p.first->left != NULL) {                 q.push(make_pair(p.first->left, p.second + 1));             }             if (p.first->right != NULL) {                 q.push(make_pair(p.first->right, p.second + 1));             }         }         return r;     } };`

### Related Puzzles

These two puzzles can in fact be solved by using the same approach. The only difference is that it asks for a reverse level order, which can simply be reversed using:

`reverse(r.begin(), r.end());`
`reverse(r.begin(), r.end());`

–EOF–

GD Star Rating