Good morning! 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
and1000000000
- 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
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);
tree4.left.left = new Node(2);
tree4.left.left.left = new Node(1);
var tree5 = new Node(8);
tree5.left = new Node(6);
tree5.right = new Node(9);
tree5.left.left = new Node(5);
tree5.left.right = new Node(7);
tree5.right.right = new Node(10);
try {
assertIsFunction(inorderTraversal, '`inorderTraversal` should be a function');
console.log('PASSED: ' + '`inorderTraversal` should be a function');
} catch (err) {
console.log(err);
}
try {
assert.deepEqual(inorderTraversal(tree2), [17, 10, 3, 5, 8]);
console.log('PASSED: ' + '`tree2` should return `[17, 10, 3, 5, 8]`');
} catch (err) {
console.log(err);
}
try {
assert.deepEqual(inorderTraversal(tree3), [3, 6]);
console.log('PASSED: ' + '`tree3` should return `[3, 6]`');
} catch (err) {
console.log(err);
}
function assertIsFunction(f) {
return typeof f === 'function';
}
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 how we would solve this problem...
How do I use this guide?
This is one of those questions where knowing the terminology is necessary. In-order
traversal visits the left child nodes first, then the root, followed by the right child (remember, it's called in-order
because the current node's value is read in-between the left and right child nodes).
Recall the following ordering types:
Inorder traversal
- First, visit all the nodes in the left subtree
- Then the root node
- Visit all the nodes in the right subtree
When to use? With a BST, the in order traversal will give the elements in ascending order, useful for problems where order matters.
1// pseudo-logic of the inorder function:
2inorder(root.left)
3display(root.data)
4inorder(root.right)

xxxxxxxxxx
function inorderTraversal(root) {
let res = [];
helper(root, res);
return res;
}
function helper(root, res) {
if (!root) {
return res;
}
helper(root.left, res);
res.push(root.val);
helper(root.right, res);
return res;
}
const root = {
val: 1,
right: {
val: 2,
left: {
val: 3
}
}
};
console.log(inorderTraversal(root));
Preorder traversal
- Visit root node
- Then go to all the nodes in the left subtree
- Visit all the nodes in the right subtree
When to use? You can use pre-order traversal to create a copy of the tree, since you can access each node before its subtrees. It's also used to get expressions on an expression tree.
1display(root.data)
2preorder(root.left)
3preorder(root.right)

Note: This algorithm is equivalent to the famous graph algorithm Depth First Search (DFS).
xxxxxxxxxx
function preorderTraversal(root) {
let res = [];
helper(root, res);
return res;
}
function helper(root, res) {
if (!root) {
return res;
}
res.push(root.val);
helper(root.left, res);
helper(root.right, res);
return res;
}
const root = {
val: 1,
left: {
val: 2
},
right: {
val: 3
}
};
console.log(preorderTraversal(root));
Postorder traversal
- Visit all the nodes in the left subtree
- Visit all the nodes in the right subtree
- Visit the root node
When to use? You can use post-order traversal to delete a tree, since you can delete all of a node's children before itself.
1postorder(root.left)
2postorder(root.right)
3display(root.data)

xxxxxxxxxx
function postorderTraversal(root) {
let res = [];
helper(root, res);
return res;
}
function helper(root, res) {
if (!root) {
return res;
}
helper(root.left, res);
helper(root.right, res);
res.push(root.val);
return res;
}
const root = {
val: 1,
left: {
val: 2
},
right: {
val: 3
}
};
console.log(postorderTraversal(root));
Complexity Analysis
Worst case scenario time complexity is O(n)
. Where n
is the number of nodes in the tree (in the worst case, we'd need to go through every node to find the value we want).
As this is the recursive solution, it will require memory in the stack for each call of the traversal functions. So on average (balanced binary tree), the space complexity is O(logn)
. And in the worst case (skewed binary tree), the space complexity will be O(n)
.
For more information on tree complexities, check out our Big O Notation Cheat Sheet.
Note: Will the space complexity be same if we use an iterative solution for the traversal? Tell us in the discussion!
One Pager Cheat Sheet
- Write a function to traverse a
binary tree
in-order and print the value of each node while it passes, while meeting the specified complexity requirements. - In-order traversal visits the left child nodes first, followed by the root, and then the right child, and is useful for obtaining ascending sorted order inBSTs.
- Preorder traversal can be used to create a copy of the tree or to get expressions from an expression tree
(equivalent to Depth First Search (DFS))
bydisplaying
the root's data and thentraversing
its left and right subtrees. - With post-order traversal,
display(root.data)
will be called after traversing both left and right subtrees of the root node, which is useful for certain operations like tree deletion. - The worst case time complexity for a recursive tree traversal is
O(n)
, and the corresponding space complexity is on averageO(logn)
(balanced binary tree) andO(n)
(skewed binary tree).
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
var assert = require('assert');
function inorderTraversal(root) {
let res = [];
helper(root, res);
return res;
}
function helper(root, res) {
if (root) {
if (root.left) {
helper(root.left, res);
}
res.push(root.val);
if (root.right) {
helper(root.right, res);
}
}
}
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);
tree4.left.left = new Node(2);
tree4.left.left.left = new Node(1);
var tree5 = new Node(8);
tree5.left = new Node(6);
tree5.right = new Node(9);
tree5.left.left = new Node(5);
tree5.left.right = new Node(7);
tree5.right.right = new Node(10);
try {
assertIsFunction(inorderTraversal, '`inorderTraversal` should be a function');
console.log('PASSED: ' + '`inorderTraversal` should be a function');
} catch (err) {
console.log(err);
}
try {
assert.deepEqual(inorderTraversal(tree2), [17, 10, 3, 5, 8]);
console.log('PASSED: ' + '`tree2` should return `[17, 10, 3, 5, 8]`');
} catch (err) {
console.log(err);
}
try {
assert.deepEqual(inorderTraversal(tree3), [3, 6]);
console.log('PASSED: ' + '`tree3` should return `[3, 6]`');
} catch (err) {
console.log(err);
}
function assertIsFunction(f) {
return typeof f === 'function';
}
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.