Last week, I was asked by an interviewer by tree traverse with both recursion and iteration. Though I had done recursion on that topic, it took me some time to the iterative solution. I rethought the problems and reviewed the final solutions, on both preorder, in-order, and postorder.
Building a tree
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
module.exports = function buildTree(nodes) {
const build = (i) => {
if (nodes[i] !== null && nodes[i] !== undefined) {
const node = new TreeNode(nodes[i]);
node.left = build(i * 2 + 1);
node.right = build((i + 1) * 2);
return node;
} else {
return null;
}
};
return build(0);
};Preorder
const buildTree = require("./build-tree.js");
const preorderRecursive = (root) => {
// root left right
const walk = (node) => {
if (!node) return;
console.log(node.val);
walk(node.left);
walk(node.right);
};
walk(root);
};
const preorderIterative = (root) => {
if (root == null) return;
let stack = [root];
while (stack.length > 0) {
let node = stack.pop();
console.log(node.val);
if (node.right !== null) {
stack.push(node.right);
}
if (node.left !== null) {
stack.push(node.left);
}
}
};
const tree = buildTree([1, 2, 3, 4, 5]);
preorderRecursive(tree);
preorderIterative(tree);Inorder
const buildTree = require("./build-tree.js");
const inorderRecursive = (root) => {
// left root right
const walk = (node) => {
if (!node) return;
walk(node.left);
console.log(node.val);
walk(node.right);
};
walk(root);
};
const inorderIterative = (root) => {
if (!root) return;
let stack = [root];
let cur = root.left;
while (1) {
if (cur !== null) {
stack.push(cur);
cur = cur.left;
} else {
if (stack.length > 0) {
cur = stack.pop();
console.log(cur.val);
cur = cur.right;
} else {
break;
}
}
}
};Postorder
const buildTree = require("./build-tree.js");
const postorderRecursive = (root) => {
// left right root
const walk = (node) => {
if (!node) return;
walk(node.left);
walk(node.right);
console.log(node.val);
};
walk(root);
};
const postorderIterativeTwoStack = (root) => {
if (root === null) return;
let s1 = [];
let s2 = [];
s1.push(root);
while (s1.length > 0) {
let node = s1.pop();
s2.push(node);
if (node.left) {
s1.push(node.left);
}
if (node.right) {
s1.push(node.right);
}
}
while (s2.length > 0) {
let node = s2.pop();
console.log(node.val);
}
};Levelorder
const recursive = (root) => {
let res = [];
const walk = (node, level) => {
if (!node) return;
if (res[level] === undefined) res[level] = [node.val];
else res[level].push(node.val);
walk(node.left, level + 1);
walk(node.right, level + 1);
};
walk(root, 0);
return res;
};
const iterative = (root) => {
let queue = [root];
let res = [];
while (queue.length > 0) {
let curLevel = [];
let len = queue.length;
for (let i = 0; i < len; i++) {
let curNode = queue.shift();
if (curNode !== null) {
curLevel.push(curNode.val);
queue.push(curNode.left);
queue.push(curNode.right);
}
}
if (curLevel.length !== 0) res.push(curLevel);
}
return res;
};