AlgoScope

Inorder Traversal

Left subtree, then the node, then the right. On a search tree that comes out sorted.

Tree algorithms, algorithm, beginner
The inorder traversal visited 20, 30, 40, 50, 60, 70, 80.20304050607080
The inorder traversal visited 20, 30, 40, 50, 60, 70, 80.20304050607080

Tree Traversals: Inorder comes out sorted

Result, step 9 of 9

The inorder walk is 20, 30, 40, 50, 60, 70, 80. Inorder on a search tree always comes out sorted.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(h)

Leads to

Topics that need this one first.

Taught by the same lesson

Tree Traversals covers these too, in the same run.