“Can you write a function to traverse a binary tree inorder, and print out
the value of each node as it passes?”
“The example would output [4, 6, 5] since there is no left child for 4, and 6
is visited inorder before 5.
The definition of a tree node is as follows:”
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
Another example tree:
Should result in [17, 10, 3, 5, 8] .
Iterating with a stack seems right for traversing a tree in order.
From a given node, we need to get to its leftmost descendent node first,
pushing each node we visit on the way on to the stack to look at afterwards.
function inorderTraversal(node) {
const result = [];
const stack = [];
while (true) {
// Keep descending left until there is no left child.
if (node) {
stack.push(node);
node = node.left;
continue;
}
// Take the most recent node back off the stack, take its value, and
// continue from its right child.
if (stack.length > 0) {
node = stack.pop();
result.push(node.val);
node = node.right;
continue;
}
// We've visited all nodes; finish.
break;
}
return result;
}
This should be O(n) .
“Follow up: you’ll likely get the recursive solution first, could you do it
iteratively?”
I actually did the iterative approach first. The recursive approach could look
like this:
function inorderTraversal(node, result = []) {
if (!node) {
return result;
}
if (node.left) {
inorderTraversal(node.left, result);
}
result.push(node.val);
if (node.right) {
inorderTraversal(node.right, result);
}
return result;
}
This is a lot more compact than the iterative version, but could exhaust the
execution stack for a large tree.
View post:
AlgoDaily 10: Binary Tree Inorder Traversal
