Binary Tree Level Order Traversal

Question

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

For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

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

Answer 1

In my last post: Printing Binary Tree in Level Order, we discuss how to print a tree using Breadth First Search (BFS). The challenge now is, can you do it using Depth First Search (DFS) this time?

Hint:
Write a function call printLevel(BinaryTree *p, int level) which will print all nodes of a given level. Assume you know the height of the tree, then you can print the entire tree level by level utilizing printLevel.

Solution:
printLevel function can be solved using DFS. Decrement level by one as you advance to the next level. When level equals 1, you've reached the given level. To find the maximum height (or the max depth) of a tree, you can read my post: Maximum Height of a Binary Tree.

void printLevel(BinaryTree *p, int level) {
    if (!p) return;
    if (level == 1) {
        cout << p->data << " ";
    } else {
        printLevel(p->left, level-1);
        printLevel(p->right, level-1);
    }
}

void printLevelOrder(BinaryTree *root) {
    int height = maxHeight(root);
    for (int level = 1; level <= height; level++) {
        printLevel(root, level);
        cout << endl;
    }
}

Further Thoughts:
If you look carefully, you will notice that the DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.

Could you find the run time complexity for the DFS level-order traversal solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?

Complexity Analysis:
Although the DFS solution traverse the same node multiple times, it is not another order slower than the BFS solution. Here is the proof that the DFS solution above runs in O(N) time, where N is the number of nodes in the binary tree and we assume that the binary tree is balanced.

We first compute the complexity of printLevel for the kth level:

T(k) = 2T(k-1) + c
     = 2^k-1 T(1) + c
     = 2^k-1 + c

Assuming it's a balanced binary tree, then it would have a total of lg N levels.

Therefore, the complexity of printing all levels is:

T(1) + T(2) + ... + T(lg N)
= 1 + 2 + 2² + ... + 2^{lg N-1} + c
= O(N)

Finding the maximum height of the tree also takes O(N) time, therefore the overall complexity is still O(N).

Answer 2

By now, you should be able to do pre-order, in-order, and post-order tree traversal off the top of your head. These are called Depth First Search (DFS), since they visit the tree by proceeding deeper and deeper until it reaches the leaf nodes.

DFS uses a data structure called Stack and is commonly implemented using recursion (since function calls are pushed and popped off the memory stack). If recursion is not allowed, we can simulate the recursion by using iterative method with the help of stack. See my older post: Binary Search Tree In-Order Traversal Iterative Solution on how to do a DFS iteratively using a stack.

The most natural solution for level-order traversal is Breadth First Search (BFS), since it visits the nodes level by level. BFS requires the use of a data structure called Queue, which is a First In First Out (FIFO) structure. If you are curious, level-order traversal can be implemented using DFS too. See my next post: Binary Tree Level-Order Traversal Using Depth First Search (DFS) for the challenge.

In order to print the binary tree in level order with newline in the end of each level, we can utilize two queues. The first queue stores the current level's nodes, while the second queue stores the next level's nodes (the current level nodes' children).

When the first queue is emptied, we know that it must have reached the end of the current level, therefore we print a newline. Then, we switch the emptied first queue with the second queue (which is populated with the next level's nodes). Then we repeat the process over again.

void printLevelOrder(BinaryTree *root) {
    if (!root) return;
    queue<BinaryTree*> currentLevel, nextLevel;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.front();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            nextLevel.push(currNode->left);
            nextLevel.push(currNode->right);
        }
        if (currentLevel.empty()) {
            cout << endl;
            swap(currentLevel, nextLevel);
        }
    }
}

Is it possible that a solution exists using only one single queue? Yes, you bet. The single queue solution requires two extra counting variables which keep tracks of the number of nodes in the current level (nodesInCurrentLevel) and the next level (nodesInNextLevel). When we pop a node off the queue, we decrement nodesInCurrentLevel by one. When we push its child nodes to the queue, we increment nodesInNextLevel by two. When nodesInCurrentLevel reaches 0, we know that the current level has ended, therefore we print an endline here.

void printLevelOrder(BinaryTree *root) {
    if (!root) return;
    queue<BinaryTree*> nodesQueue;
    int nodesInCurrentLevel = 1;
    int nodesInNextLevel = 0;
    nodesQueue.push(root);
    while (!nodesQueue.empty()) {
        BinaryTree *currNode = nodesQueue.front();
        nodesQueue.pop();
        nodesInCurrentLevel--;
        if (currNode) {
            cout << currNode->data << " ";
            nodesQueue.push(currNode->left);
            nodesQueue.push(currNode->right);
            nodesInNextLevel += 2;
        }
        if (nodesInCurrentLevel == 0) {
            cout << endl;
            nodesInCurrentLevel = nodesInNextLevel;
            nodesInNextLevel = 0;
        }
    }
}

Answer 3

vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int> > ret;
    dfs(root,0,ret);
    return ret;
}
void dfs(TreeNode *root, int level, vector<vector<int> > &ret) {
    if(!root)return ;
    if(level>=ret.size()) ret.push_back(vector<int>());
    ret[level].push_back(root->val);
    dfs(root->left,level+1,ret);
    dfs(root->right,level+1,ret);
}

Answer 4

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > result;
        if(root == NULL) return result;

        vector<int> level;
        queue<pair<TreeNode *, int> > ltvs;
        int cl = 0; 
        pair<TreeNode *, int> tmp;
        if(root->left != NULL) {
            tmp.first = root->left; 
            tmp.second = 1;
            ltvs.push(tmp);
        }
        if(root->right != NULL) {
            tmp.first = root->right;
            tmp.second = 1;
            ltvs.push(tmp);
        }
        level.push_back(root->val);
        while(!ltvs.empty()) {
            tmp = ltvs.front();
            ltvs.pop();
            if(tmp.second != cl) {
                cl = tmp.second;
                result.push_back(level);
                level.resize(0);
            }
            level.push_back((tmp.first)->val);
            if((tmp.first)->left != NULL) 
                ltvs.push(pair<TreeNode *, int>((tmp.first)->left, tmp.second+1));
            if((tmp.first)->right != NULL) 
                ltvs.push(pair<TreeNode *, int>((tmp.first)->right, tmp.second+1));
        }

        result.push_back(level);
        return result;
    }
};

Answer 5

I also used two queues to perform BFS. But the difference is that one queue is used to store the nodes, while the other queue is used to store the levels of the nodes.

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
    if(root==null)
        return result;
    ArrayList<TreeNode> trees=new ArrayList<TreeNode>();
    ArrayList<Integer> levels=new ArrayList<Integer>();
    trees.add(root);
    levels.add(1);
    ArrayList<Integer> root_level=new ArrayList<Integer>();
    root_level.add(root.val);
    result.add(root_level);
    while(!trees.isEmpty())
    {
        TreeNode top=trees.remove(0);
        int curr_depth=levels.remove(0);
        if(top.left!=null)
        {
            trees.add(top.left);
            levels.add(curr_depth+1);
        }
        if(top.right!=null)
        {
            trees.add(top.right);
            levels.add(curr_depth+1);
        }
        int size=levels.size();
        if(size>0 && levels.get(0)==levels.get(size-1) && (curr_depth==levels.get(0)-1))
        {
            ArrayList<Integer> temp=new ArrayList<Integer>();
            for(int i=0;i<size;i++)
            {
                temp.add(trees.get(i).val);
            }
            result.add(temp);
        }
    }

    return result;
}

Answer 6

vector<vector<int> > levelOrder(TreeNode *root) {

    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int>> ret;
    if( root == NULL )
        return ret;
    vector<int> tmp;
    ret.push_back(tmp);
    queue<TreeNode*> q;
    q.push(root);
    int nCnt = q.size();

    while( !q.empty() )
    {
        nCnt--;
        TreeNode* p = q.front();
        q.pop();
        ret[ret.size()-1].push_back(p->val);
        if( p->left )
            q.push(p->left);
        if( p->right )
            q.push(p->right);

        if( nCnt == 0 && !q.empty() )
        {
            nCnt = q.size();
            vector<int> tmp;
            ret.push_back(tmp);
        }

    }
    return ret;
}

Answer 7

vector<vector<int> > levelOrder(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int>> levels;
    queue<TreeNode *> q;
    if (!root)
        return levels;
    q.push(root);
    while(!q.empty()) {
        vector<int> l;
        vector<TreeNode *> temp;
        while(!q.empty()) {
            TreeNode *p = q.front();
            q.pop();
            l.push_back(p->val);
            if (p->left) temp.push_back(p->left);
            if (p->right) temp.push_back(p->right);
        }
        levels.push_back(l);
        for (int i=0; i<temp.size(); i++)
            q.push(temp[i]);
    }
    return levels;
}

Answer 8

Put all nodes into a queue in tree level sequence. Once a single line is parsed, insert a seperator into the queue. During traversing the queue from head to tail, when we see a seperator, we know it begins a new line.

vector<vector<int> > levelOrder(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    std::list<int> queue;
    std::vector<int> single_level;
    std::vector<vector<int> > node_levels;

    if (!root) {
        return node_levels;
    }

    queue.push_back((int)root);
    queue.push_back(INT_MIN);
    single_level.push_back(root->val);
    node_levels.push_back(single_level);
    single_level.clear();

    while (!queue.empty()) {
        if (queue.front() == INT_MIN) {
            queue.pop_front();
            queue.push_back(INT_MIN);
            if (queue.front() == INT_MIN) {
                break;
            }
            node_levels.push_back(single_level);
            single_level.clear();

            continue;
        }

        TreeNode *node = (TreeNode*)queue.front();
        queue.pop_front();

        if (node->left) {
            queue.push_back((int)node->left);
            single_level.push_back(node->left->val);
        }
        if (node->right) {
            queue.push_back((int)node->right);
            single_level.push_back(node->right->val);
        }
    } // while

    return node_levels;
}

Answer 9

Make my code a little simpler.

vector<vector<int> > levelOrder(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    std::list<int> queue;
    std::vector<int> single_level;
    std::vector<vector<int> > node_levels;

    if (!root) {
        return node_levels;
    }

    queue.push_back((int)root);
    queue.push_back(INT_MIN);

    while (!queue.empty()) {
        if (queue.front() == INT_MIN) {
            queue.pop_front();
            queue.push_back(INT_MIN);
            node_levels.push_back(single_level);
            single_level.clear();

            if (queue.front() == INT_MIN) {
                break;
            }

            continue;
        }

        TreeNode *node = (TreeNode*)queue.front();
        queue.pop_front();

        single_level.push_back(node->val);

        if (node->left) {
            queue.push_back((int)node->left);
        }
        if (node->right) {
            queue.push_back((int)node->right);
        }
    } // while

    return node_levels;
}

Answer 10

use dfs to travelsal the tree, and use a point to record new level's first node

    vector<vector<int> > result;
    if (root == NULL) {
        return result;
    }
    queue<TreeNode*> q;
    q.push(root);
    TreeNode* new_level_flag = root->left;
    if (new_level_flag == NULL) {
        new_level_flag = root->right;
    }
    vector<int> brothers;
    brothers.push_back(root->val);
    while(!q.empty()) {
        TreeNode* top = q.front();
        q.pop();
        if (top->left != NULL) {
            q.push(top->left);
            if (top->left == new_level_flag) {
                result.push_back(brothers);
                brothers.clear();
                new_level_flag = NULL;
            }
            brothers.push_back(top->left->val);
            if (new_level_flag == NULL) {
                new_level_flag = top->left->left==NULL?top->left->right:top->left->left;
            }
        }
        if (top->right != NULL) {
            q.push(top->right);
            if (top->right == new_level_flag) {
                result.push_back(brothers);
                brothers.clear();
                new_level_flag = NULL;
            }
            brothers.push_back(top->right->val);
            if (new_level_flag == NULL) {
                new_level_flag = top->right->left==NULL?top->right->right:top->right->left;
            }
        }
    }
    if (!brothers.empty()) {
        result.push_back(brothers);
    }
    return result;

Binary Tree Level Order Traversal

Follow this question

Welcome to LeetCode

Related questions