LOGBOOK

HELP

Quiz Entry - updated: 2026.09.29

How does an inorder traversal of a binary tree work, and how can it be used to draw a binary tree?

Inorder visits a node after its left subtree and before its right subtree. Drawing each node at $x$ = its inorder rank and $y$ = its depth gives a layout where every node has its own column and every left subtree lies to the left of its parent.

A binary tree drawn with x = inorder rank and y = depth

* Each node gets its own column, and every left subtree sits to the left of its parent. *

Algorithm inOrder(v)
  if hasLeft(v)
    inOrder(left(v))
  visit(v)
  if hasRight(v)
    inOrder(right(v))

Inorder only exists for binary trees: "between the left and the right subtree" needs exactly two sides.

Drawing a tree with it. Number the nodes in the order inorder visits them and use that number as the $x$-coordinate; use the depth as the $y$-coordinate. Everything in a node's left subtree is visited before the node, so it gets smaller $x$ values and lands to the left; everything in the right subtree lands to the right. Since each node has a unique inorder rank, no two nodes share a column and nothing overlaps.

That same property, "left subtree, then node, then right subtree", is what makes inorder print the keys of a binary search tree in sorted order.

From Quiz: ADS / Trees: Structure, Storage and Traversals | Updated: Sep 29, 2026