Skip to main content

Binary Tree Level Order Traversal

Problem​

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    map<int, vector<int>> mp;

   public:
    void traverse(TreeNode* root, int h) {
        if (!root) return;
        mp[h].push_back(root->val);
        traverse(root->left, h + 1);
        traverse(root->right, h + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        traverse(root, 0);
        for (auto i : mp) ans.push_back(i.second);
        return ans;
    }
};