DEV Community

Ayan Banerjee
Ayan Banerjee

Posted on • Originally published at csposts.com on

2 1

Interview Problem: Binary Tree Reverse Level Order Traversal

Given a binary tree, print its reverse level order traversal. For example, given this tree -

    3
   / \
  2   8
     / \
    1   9
Enter fullscreen mode Exit fullscreen mode

print -

[
    [1, 9],
    [2, 8],
    [3]
]
Enter fullscreen mode Exit fullscreen mode

Approach - 1: BFS

We can simply perform a BFS traversal and reverse the resulting traversal.

animated-bfs

By Blake Matheny - Transferred from en.wikipedia to Commons., CC BY-SA 3.0, Link

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> bfsTraversal;
    // perform bfs
    queue<TreeNode*> q;
    if (root) q.push(root);
    while(!q.empty()) {
        int levelSize = q.size();
        vector<int> curLevelTraversal(levelSize);
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* current = q.front();
            q.pop();
            curLevelTraversal[i] = current -> val;
            if (current -> left) q.push(current -> left);
            if (current -> right) q.push(current -> right);
        }
        bfsTraversal.push_back(curLevelTraversal);
    }
    reverse(bfsTraversal.begin(), bfsTraversal.end());
    return bfsTraversal;
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(N) due to BFS

Space Complexity: O(N) as we are storing nodes in the queue

Approach - 2: DFS

This problem can also be solved using DFS. It’s important that we should visit the left child first and then the right child. As we go from a parent node to its child nodes, we increase the level. We also store them in a vector and return its reverse.

void dfs(TreeNode *node, vector<vector<int>> &reverseLevelTraversal, int level) {
    if (node == nullptr) return;
    if (level >= reverseLevelTraversal.size()) {
        reverseLevelTraversal.push_back({});
    }
    reverseLevelTraversal[level].push_back(node -> val);
    // increase level if when we go to children nodes
    dfs(node -> left, reverseLevelTraversal, level + 1);
    dfs(node -> right, reverseLevelTraversal, level + 1);
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> reverseLevelTraversal;
    // start with level 0
    dfs(root, reverseLevelTraversal, 0);
    reverse(reverseLevelTraversal.begin(), reverseLevelTraversal.end());
    return reverseLevelTraversal;
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(N) due to DFS

Space Complexity: O(N) for recursion stack space

Exercise: Use stack to perform DFS.

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay