AlgoDaily 10: Binary Tree In-order Traversal

“Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes?”

  4
   \
    5
   /
  6

“The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order 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:

     05 
    /  \ 
   10  08 
  /  \ 
 17  03 

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 left-most 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.


Tech mentioned