import { TreeNode } from “./TreeNode”;
import {BinaryTree} from “./BinaryTree”;
import Deque from “./deque”;
function zigzagLevelOrder(root) {
if (root == null) return [];
let results = [],
dq = new Deque(),
reverse = false;
dq.push(root);
while (dq.length > 0) {
let size = dq.length;
results.push([]);
for (let i = 0; i < size; i++) {
if (reverse == false) {
let node = dq.shift();
results[results.length - 1].push(node.data);
if (node.left != null) {
dq.push(node.left);
}
if (node.right != null) {
dq.push(node.right);
}
} else {
let node = dq.pop();
results[results.length - 1].push(node.data);
if (node.right != null) dq.unshift(node.right);
if (node.left != null) dq.unshift(node.left);
}
}
reverse = !reverse;
}
return results;
}
// Driver code
function main() {
const input1 = [new TreeNode(100), new TreeNode(50), new TreeNode(200), new TreeNode(25), new TreeNode(75), new TreeNode(350)]
tree1 = new BinaryTree(input1);
const input2 = [new TreeNode(25), new TreeNode(50), new TreeNode(75), new TreeNode(100), new TreeNode(200), new TreeNode(350)]
tree2 = new BinaryTree(input2);
const input3 = [new TreeNode(350), new TreeNode(200), new TreeNode(100), new TreeNode(75), new TreeNode(50), new TreeNode(25)],
tree3 = new BinaryTree(input3);
tree4 = new BinaryTree([new TreeNode(100)]);
roots = [tree1.root, tree2.root, tree3.root, tree4.root, null];
for (let i = 0; i < roots.length; i++) {
console.log(i + 1 + ".\tBinary Tree:");
displayTree(roots[i]);
// Printing the in-order list using the method we just implemented
console.log("\n\tThe zigzag level order traversal is: ", zigzagLevelOrder(roots[i]));
console.log("\n", "-".repeat(100), "\n");
}
}
main();
Course: Grokking Coding Interview Patterns in JavaScript - Learn Interactively
Lesson: Solution: Binary Tree Zigzag Level Order Traversal