C# || How To Traverse Binary Tree Zigzag Level Order Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to traverse binary tree zigzag level order using C#.

1. Zigzag Level Order – Problem Statement

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

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

2. Zigzag Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree zigzag level order.

This solution uses Breadth First Search to explore items at each level.





		
		
			2. Zigzag Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();

        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }

        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();

            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();

                level.Add(current.val);
                queue.Enqueue(current);
            }

            // Add level to result
            result.Add(level);

            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();

                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();
 
        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }
 
        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();
 
            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();
 
                level.Add(current.val);
                queue.Enqueue(current);
            }
 
            // Add level to result
            result.Add(level);
 
            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();
 
                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

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

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: binary search, c-sharp, leetcode

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories