I'm using queue to iteratively solve a BST preorder traversal question. I know for stack, it's reversed and it works, but with queue I'm getting the wrong answer. Why? Thanks
var preorderTraversal = function(root) {
if (root == null) {
return [];
}
const queue = [];
const result = [];
queue.unshift(root);
while(queue.length > 0) {
let current = queue.shift();
result.unshift(current.val);
if (current.right) queue.unshift(current.right);
if (current.left) queue.unshift(current.left);
}
return result;
};
You are using queue as a stack, since you shift values in and out at one and the same side of the array, which is what a stack does ("LIFO (last in, first out)"). So it actually works, but as you state at the start, it works in reverse because you prepend the values to the result. If you would append them, it would be fine:
var preorderTraversal = function(root) {
if (root == null) {
return [];
}
const queue = [];
const result = [];
queue.unshift(root);
while(queue.length > 0) {
let current = queue.shift();
result.push(current.val); // Append instead of prepend
if (current.right) queue.unshift(current.right);
if (current.left) queue.unshift(current.left);
}
return result;
};
// Add the Node class to facilitating creating a binary tree (a binary search tree)
class Node {
constructor(val) {
this.val = val;
this.left = this.right = null;
}
add(val) {
if (val < this.val) {
if (this.left) this.left.add(val);
else this.left = new Node(val);
} else {
if (this.right) this.right.add(val);
else this.right = new Node(val);
}
}
print(tab="") {
if (this.right) this.right.print(" " + tab);
console.log(tab + this.val);
if (this.left) this.left.print(" " + tab);
}
}
// Demo
let root = new Node(4);
for (let val of [2, 6, 1, 3, 5, 7]) root.add(val);
console.log("The tree (with root at the far left): ");
root.print(); // Print the tree
console.log("preorder traversal: ", ...preorderTraversal(root));Again, this is a stack solution, not a queue solution -- despite the variable name. JavaScript array methods give a "deque" interface to arrays, and so you can easily add and remove elements from either side of the array.
If you exclusively use push and pop you'll have a stack behaviour, and if you replace those with unshift and shift, you'll still have a stack behaviour.
You'll get a queue behaviour when you use the pair push/shift or the pair unshift/pop, but that will not be useful for implementing a pre order traversal. That is what you would use for a level order (breadth-first) traversal.