Binary tree inorder traversal

Easy TimeO(n) SpaceO(h)

In-order means visiting everything in a node's left subtree, then the node itself, then everything in its right subtree — the same three steps at every node, all the way down. Given the root of a binary tree, return its values in that order. Every node is visited exactly once, and an empty tree produces an empty list. Over a binary search tree the result comes out sorted.

Examples

Example 1

Input
node = buildTree()out = []
Output
[1,2,3,4,6,7,9]
The left subtree 1, 2, 3, then the root 4, then the right subtree 6, 7, 9.

Example 2

Input
node = buildTree().leftout = []
Output
[1,2,3]
The same three steps inside the left subtree alone: 1, then 2, then 3.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function inorder(node, out) {
  if (node === null) return out;
  inorder(node.left, out);
  out.push(node.val);
  inorder(node.right, out);
  return out;
}
inorder(buildTree(), []);
Done

The first 8 calls, of 16. This one does not fit on a page.

Step through inorder(buildTree(), []) call by call

More like this

All binary trees examples (9) →