Pattern visualizer

Morris Inorder Traversal

A normal inorder traversal needs somewhere to remember 'come back to this ancestor once its left subtree is done' — that's what the call stack (or an explicit stack) is for. Morris traversal gets the same return trip for free: before descending into a node's left subtree, it finds that subtree's rightmost node (the node's inorder predecessor) and threads its right pointer to point back at the current node. Arriving at the predecessor later, the thread is exactly where the traversal needs to go next — so it is followed, then cut, restoring the tree to its original shape. Animated on: Given the root of a binary tree, return the inorder traversal of its nodes' values using O(1) extra space — no stack, no recursion — for the tree [1,2,3,4,5] (root 1, left 2 with children 4 and 5, right 3)..

No stack, no recursion — a temporary thread back to the current node stands in for the call-stack frame.

time O(n)space O(1)step 1 / 15

line 9

At 1, a left child exists, so 1 cannot be recorded yet. Its inorder predecessor — found by walking right pointers from 2 — is 5.

Pseudocode

1FUNCTION morrisInorder(root):
2  cur <- root
3  out <- []
4  WHILE cur != null:
5    IF cur.left = null:
6      APPEND cur.val TO out
7      cur <- cur.right
8    ELSE:
9      pred <- RIGHTMOST(cur.left, cur)
10      IF pred.right = null:
11        pred.right <- cur
12        cur <- cur.left
13      ELSE:
14        pred.right <- null
15        APPEND cur.val TO out
16        cur <- cur.right
17  RETURN out

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap