pattern heroPT–23LeetCode Extension

Tree traversals

Walk the tree with recursion: left subtree, right subtree and the node itself. The three walks differ only in when the node is handled: before its children, between them or after them.

Variant
P16 Tree traversalsIn-order · 1×

Example problem: list the values of a binary search tree in sorted order. Each node is an object with val, left and right; everything in the left subtree is smaller than the node, everything in the right one is larger.

nonenonenonenonenonenone84121014out—call stacktop on the right8
not visited yetwaiting on the call stackcurrent callfinished, #n is its place in outnone: an empty child

8 is a node, not none: visit it

node = 8out = []
01/37
restart · back · play · step
Speed
1function inorder(node, out):
2 if node is none:
3 return
4 inorder(node.left, out)
5 out.add(node.val)
6 inorder(node.right, out)

← → step · space play/pause

How to recognise

a tree problem where the order you meet the nodes matters: sorted values or the k-th smallest in a BST (in-order), copying or saving a tree (pre-order), sizes, heights and deleting (post-order).

How to solve problems like this

  1. Pick the order by when a node needs its work done: before its children (pre), between them (in) or after them (post).
  2. Write f(node). If node is none, return.
  3. Put the node's own work before, between or after the calls f(node.left) and f(node.right).
  4. In a BST, in-order gives the values sorted: use it for the k-th smallest, to check that a tree is a BST, or to compare neighbours.

Where it's used

  • Deleting a folder. rm -r cannot delete a folder while something is in it, so it deletes the contents first and the folder after. That is post-order.
  • Web pages. document.querySelectorAll returns elements in document order: an element, then its children in turn. That is a pre-order walk of the HTML tree.
  • Compilers. To work out (2 + 3) × 4 you need both operands before the operation, so the expression tree is walked in post-order. Python bytecode looks just like that: load the operands, then the operation.