AlgoVerse

Threaded binary tree

Point each empty right link of the tree at the node's inorder successor (a thread); then an inorder walk needs no stack and no recursion.

A binary tree with n nodes has n + 1 null links. Perlis and Thornton proposed putting them to use: each empty right link points at the node's inorder successor. These links are called threads. (The full version also points empty left links at the inorder predecessor.)

Read the full explanation ↓
Input:
n=7PDF export

A seven-node search tree; three threads are drawn (3→6, 7→15 and 17→18) and the walk gives 3 6 7 15 17 18 20 without a stack.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  6. self.thread = None # used only when right is empty: the inorder successor
  9. def threaded(root):
  10. # Phase 1: an inorder walk; every node with an empty right link gets a thread to its successor.
  11. stack = []
  12. prev = None
  13. node = root
  14. while node is not None or stack:
  15. if node is not None:
  16. stack.append(node)
  17. node = node.left
  18. else:
  19. node = stack.pop()
  20. if prev is not None and prev.right is None:
  21. prev.thread = node
  22. prev = node
  23. node = node.right
  24. # Phase 2: inorder again, with no stack: follow a thread, or go right and then all the way left.
  25. out = []
  26. node = root
  27. while node is not None and node.left is not None:
  28. node = node.left
  29. while node is not None:
  30. out.append(node.key)
  31. if node.right is None:
  32. node = node.thread
  33. else:
  34. node = node.right
  35. while node.left is not None:
  36. node = node.left
  37. return out

Invariant: During the walk, every node without a right link reaches the next inorder node directly through its thread.

Start

36715171820

Local variables

Orange = changed in this step

root object

  • key = 15
  • left = Node(key=6, left=Node(key=3, left=None, right=None, thread=None), right=Node(key=7, left=None, right=None, thread=None), thread=None)
  • right = Node(key=18, left=Node(key=17, left=None, right=None, thread=None), right=Node(key=20, left=None, right=None, thread=None), thread=None)
  • thread = None

Call stack

  1. threaded()line 9
Step 1 of 120
Black = thread, visit · Orange = key stepthread: 0/3 · start_walk: 0/1 · down_left: 0/3 · visit: 0/7 · by_thread: 0/4 · go_right: 0/3
    Explanation

    The idea

    A binary tree with n nodes has n + 1 null links. Perlis and Thornton proposed putting them to use: each empty right link points at the node's inorder successor. These links are called threads. (The full version also points empty left links at the inorder predecessor.)

    A walk without a stack

    With threads, the next inorder node is easy to find from any node:

    • if it has a right child: one step right, then as far left as possible;
    • otherwise: follow its thread.

    So the inorder walk runs without a stack and without recursion.

    In practice

    We need to know whether a right link is a real child or a thread. Textbooks keep a flag bit in each node for that; here the thread lives in a separate field, thread. Threads are drawn dashed.