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
- LeetCode 94Binary Tree Inorder TraversalReading a family tree left, parent, right
- LeetCode 145Binary Tree Postorder TraversalPacking up: children before parents
- LeetCode 101Symmetric TreeHolding a tree up to a mirror
- LeetCode 104Maximum Depth of Binary TreeHow deep does the folder tree go?
- LeetCode 110Balanced Binary TreeIs the hanging mobile balanced?
- LeetCode 124Binary Tree Maximum Path SumThe richest trail through a tree of coins
- LeetCode 530Minimum Absolute Difference in BSTThe closest two prices in a sorted tree
NeetCode 150 problems that use it
Trees · Tries ·
- LeetCode 226 · EasyInvert Binary TreeFlipping a mobile in a mirror
- LeetCode 104 · EasyMaximum Depth of Binary TreeHow deep does the folder tree go?
- LeetCode 543 · EasyDiameter of Binary TreeThe longest walk between two leaves
- LeetCode 110 · EasyBalanced Binary TreeIs the hanging mobile balanced?
- LeetCode 100 · EasySame TreeTwo gardeners comparing their trees
- LeetCode 572 · EasySubtree of Another TreeSpotting a small branch pattern inside a big tree
- LeetCode 235 · MediumLowest Common Ancestor of a Binary Search TreeWhere two relatives’ family lines split
- LeetCode 102 · MediumBinary Tree Level Order TraversalA family photo, one generation per row
- LeetCode 199 · MediumBinary Tree Right Side ViewWhat you see standing to the right of the tree
- LeetCode 1448 · MediumCount Good Nodes in Binary TreeA hiker counting viewpoints with no taller peak behind
- LeetCode 98 · MediumValidate Binary Search TreeEvery branch has a fence of allowed values
- LeetCode 230 · MediumKth Smallest Element in a BSTCounting library shelves in order
- LeetCode 105 · MediumConstruct Binary Tree from Preorder and Inorder TraversalRebuilding a family tree from two lists
- LeetCode 124 · HardBinary Tree Maximum Path SumThe richest trail through a tree of coins
- LeetCode 297 · HardSerialize and Deserialize Binary TreePacking a tree into a parcel tape and unpacking it
- LeetCode 208 · MediumImplement Trie (Prefix Tree)A letter tree that grows as words are added
- LeetCode 211 · MediumDesign Add and Search Words Data StructureA trie where a dot means “any letter”
- LeetCode 212 · HardWord Search IIA word-search puzzle guided by a trie