Home
Binary Tree Zigzag Level Order Traversal Algorithms using DFS and BFS
Tags:, , , , ,

Binary Tree Zigzag Level Order Traversal Algorithms using DFS and BFS

September 26, 2019 No Comments algorithms, BFS, c / c++, DFS, recursive

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

1
2
3
4
5

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

We can accomplish the task by using DFS or BFS algorithms where in DFS, we require tracking the levels (passing the depth value down the tree) and in BFS, we inherently expand the tree level by level.

Depth First Search (Recursion) Algorithm to Zigzag Level Order Traval the Binary Tree

Let’s pass the depth of the node when doing recursive depth first search. And we can use the depth to output the order to the corresponding index of the result vector. By checking if the depth is odd or even, we know that particular level should be in reverse order or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    
    void dfs(TreeNode* root, int depth) {
        if (root == nullptr) return;
        if (res.size() <= depth) {
            res.push_back({});
        }
        if (depth % 2 == 0) {
            res[depth].push_back(root->val);
        } else {
            res[depth].insert(begin(res[depth]), root->val);
        }        
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);        
    }
};
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
private:
    vector<vector<int>> res;
    
    void dfs(TreeNode* root, int depth) {
        if (root == nullptr) return;
        if (res.size() <= depth) {
            res.push_back({});
        }
        if (depth % 2 == 0) {
            res[depth].push_back(root->val);
        } else {
            res[depth].insert(begin(res[depth]), root->val);
        }        
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);        
    }
};

We can use the std::vector().push_back to append an element to the vector or std::vector.insert() together with the begin() vector to insert an element to the front of a vector.

The time complexity for DFS is O(N) where each node is visited exactly once. The space complexity is O(N) where N is the number of the nodes in the tree (considering the tree can be just a linked list hence Height = N for recursion). Here, we don’t consider the output vector, which clearly requires O(N^2) space.

How to do Zigzag Level Order Traversal for a Binary Tree using Breadth First Search Algorithm?

The iterative approach could be using the BFS (breadth first search) where we pop all elements from the queue (which belong to the same level), and push their children (which will be of the same level as well).

The level is recorded while we expand the tree using BFS level by level. We can reverse the level vector using std::reverse()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                r.push_back(p->val);
            }                
            if (level % 2 == 1) {
                std::reverse(begin(r), end(r));
            }
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                r.push_back(p->val);
            }                
            if (level % 2 == 1) {
                std::reverse(begin(r), end(r));
            }
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};

Alternatively, we can decide to push to the back or insert to the front of the level vector depending on the oddness of the level – This approach/implementation is slightly faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                if (level % 2 == 0) {
                    r.push_back(p->val);
                } else {
                    r.insert(begin(r), p->val);
                }
            }                
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};
/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        if (root == nullptr) return res;
        Q.push(root);        
        int level = 0;
        while (!Q.empty()) {
            int num = Q.size();
            vector<int> r;
            for (int i = 0; i < num; ++ i) {
                auto p = Q.front();
                Q.pop();
                if (p->left) Q.push(p->left);
                if (p->right) Q.push(p->right);
                if (level % 2 == 0) {
                    r.push_back(p->val);
                } else {
                    r.insert(begin(r), p->val);
                }
            }                
            if (!r.empty()) {
                res.push_back(r);
            }
            level ++;
        }
        return res;
    }
};

The time complexity for BFS is also O(N). Below is the Python Implemetation of the same algorithm using BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        q = [root]
        level = 0
        while len(q) > 0:
            cur = []
            level += 1            
            sz = len(q)
            for i in range(sz):
                cur.append(q[i].val)
                if q[i].left:
                    q.append(q[i].left)
                if q[i].right:
                    q.append(q[i].right)                
            for i in range(sz):
                q.pop(0)
            if level % 2 == 0:
                cur.reverse()
            res.append(cur)
        return res
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        q = [root]
        level = 0
        while len(q) > 0:
            cur = []
            level += 1            
            sz = len(q)
            for i in range(sz):
                cur.append(q[i].val)
                if q[i].left:
                    q.append(q[i].left)
                if q[i].right:
                    q.append(q[i].right)                
            for i in range(sz):
                q.pop(0)
            if level % 2 == 0:
                cur.reverse()
            res.append(cur)
        return res

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
921 words
Last Post: Counting the Prime Arrangements
Next Post: The Next Permutation Algorithm in C++ (std::next_permutation)

The Permanent URL is: Binary Tree Zigzag Level Order Traversal Algorithms using DFS and BFS

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  3. Three ways of Running a continuous NodeJS Application on Your Server Let’s say, I have an application that is written in NodeJs, that process the latest...
  4. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  5. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...
  6. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  7. Microbit Programming: Snake Game with Growing Body and Greedy Strategy Last week, we show the possibility of playing a simple Snake Game on the Microbit...
  8. The Review of cozmo robot from Anki The ANKI COZMO robot is fun – I got it from Amazon and it is...

Leave a Reply