DSA Tracker

Visualize

Binary Tree Inorder Traversal (Binary Trees)

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)

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.

Details

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).

Problem:Binary Tree Inorder Traversal (Binary Trees)Easy

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

step 1 / 15

4
2
5
1
3

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

Every step in words

Show all 15 steps
  1. At 1, a left child exists, so 1 cannot be recorded yet. Its inorder predecessor — found by walking right pointers from 2 — is 5.
  2. 5's right pointer is free, so thread it to 1 — a temporary bridge back, standing in for the stack frame a normal traversal would push. Step left into 2.
  3. At 2, a left child exists, so 2 cannot be recorded yet. Its inorder predecessor — found by walking right pointers from 4 — is 4.
  4. 4's right pointer is free, so thread it to 2 — a temporary bridge back, standing in for the stack frame a normal traversal would push. Step left into 4.
  5. At 4, there is no left child, so nothing needs to be revisited later — record 4 right away.
  6. 4 recorded (1st value). Step right to 2 — following the thread just used.
  7. At 2, a left child exists, so 2 cannot be recorded yet. Its inorder predecessor — found by walking right pointers from 4 — is 4.
  8. 4's right pointer already points back to 2 — the thread has done its job (the entire left subtree of 2 is done). Cut it and record 2.
  9. At 5, there is no left child, so nothing needs to be revisited later — record 5 right away.
  10. 5 recorded (3rd value). Step right to 1 — following the thread just used.
  11. At 1, a left child exists, so 1 cannot be recorded yet. Its inorder predecessor — found by walking right pointers from 2 — is 5.
  12. 5's right pointer already points back to 1 — the thread has done its job (the entire left subtree of 1 is done). Cut it and record 1.
  13. At 3, there is no left child, so nothing needs to be revisited later — record 3 right away.
  14. 3 recorded (5th value). Step right.
  15. cur is now null: every node was recorded exactly once, giving [4, 2, 5, 1, 3] — and not one stack frame or extra array was used to get back up the tree.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Inorder Traversal (Binary Trees) in the editorAll Binary Trees problemsBack to roadmap