Core pattern

Trees · DFS: walking a folder tree

Learn the trees · dfs pattern through one picture you won’t forget, worked on Preorder / Inorder / Postorder.

The example problem

Visit every node of a binary tree in preorder (node, left, right), inorder (left, node, right) or postorder (left, right, node).

Input:  folders src → (app → ui, api), (lib → test, utils), order = pre
Output: src, app, ui, api, lib, test, utils

Picture it

Picture a folder tree on a computer. The three walks differ only in when you write a folder’s name: preorder writes it when you first open the folder, inorder between its left and right subfolders, postorder when you close it after finishing everything inside.

The key idea

Same depth-first walk, three positions to “visit” the node. Each is O(n).

Python

def walk(node, out):     # preorder
    if not node:
        return
    out.append(node.name)       # visit
    walk(node.left, out)
    walk(node.right, out)

Practise trees · dfs

NeetCode 150 problems that use it

Trees · Tries ·