DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
Tree Algorithms algorithms

Tree Algorithms

Binary Tree Inorder Traversal

Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.

Worst O(n)Space O(h)
Open visualizer

1Detailed explanation

Inorder traversal visits a binary tree in the order Left subtree → Node → Right subtree. The recursive definition is short, but the call stack does a lot of work: every call waits for its left child's call to finish before visiting its own node.

On a Binary Search Tree, inorder traversal returns the values in ascending order — a fact used to validate BSTs and to find the k-th smallest element.

Recursion depth equals the tree height h, so extra space is O(h): O(log n) for balanced trees but O(n) for a skewed tree.

2Pseudocode

procedure inorder(node, result)
  if node = null
    return
  inorder(node.left, result)
  result.append(node.value)
  inorder(node.right, result)

3Interactive visualization

Binary Tree Inorder Traversalinteractive Open full visualizer
4261357
result =[]
Current callOn the call stackBeing visitedVisited

Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.

1 / 67

4Implementations

Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function inorder(node, result) {
  if (node === null) {
    return;
  }
  inorder(node.left, result);
  result.push(node.value);
  inorder(node.right, result);
}

function buildTree(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1;
  while (queue.length > 0 && i < values.length) {
    const node = queue.shift();
    if (i < values.length && values[i] !== null) {
      node.left = new TreeNode(values[i]);
      queue.push(node.left);
    }
    i++;
    if (i < values.length && values[i] !== null) {
      node.right = new TreeNode(values[i]);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

const root = buildTree([4, 2, 6, 1, 3, 5, 7]);
const result = [];
inorder(root, result);
console.log("Inorder:", result);

5Time and space complexity

Time
Best caseO(n)
Average caseO(n)
Worst caseO(n)
Space
AuxiliaryO(h)
InputO(n)
TotalO(n)

Time: Every node is visited exactly once and each call does O(1) work besides its recursive calls. There are n node calls plus n+1 calls on empty (null) children → O(n).

Space: The recursion stack holds one frame per level on the current path, so auxiliary space is O(h) where h is the tree height: O(log n) for a balanced tree, O(n) for a skewed (linked-list-like) tree. The result list adds O(n).

6Common interview variations

  • Iterative inorder with an explicit stack.
  • Morris traversal in O(1) extra space.
  • Validate a Binary Search Tree.
  • k-th smallest element in a BST.
  • Preorder and postorder traversals.

On this page

  1. 01Detailed explanation
  2. 02Pseudocode
  3. 03Interactive visualization
  4. 04Implementations (JS · Python · Java · Go)
  5. 05Time and space complexity
  6. 06Common interview variations