Good afternoon! Here's our prompt for today.

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

1  4
2   \
3    5
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:

1function Node(val) {
2  this.val = val;
3  this.left = null;
4  this.right = null;
5}

Follow up: you'll likely get the recursive solution first, could you do it iteratively?

Constraints

• Number of vertices in the tree <= 100000
• The values of the vertices in the tree will be between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

  assertIsFunction(inorderTraversal, '`inorderTraversal` should be a function');

var assert = require('assert');

​

function inorderTraversal(root) {

  return root;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

​

var tree4 = new Node(5);

tree4.left = new Node(3);

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?