Topic notebook / 04
Trees & traversal
A tree connects parents to any number of children. A queue explores it level by level; recursion explores one branch at a time.
What to look for
- Decide between breadth-first and depth-first order.
- Separate one level from the next.
- Handle an empty root.
Work through a question
14 availableScan the Warehouse Shelves
A warehouse directory has a name and any number of child shelves, not just two. Return the shelf names grouped by depth, preserving the order of children.
Medium / Breadth-first search / interactiveFind the Deepest Storage Route
A storage directory has named nodes with any number of children. Return the names along a root-to-leaf route with the most nodes. For tied depths, choose the first route in left-to-right child order. Return [] for an empty directory.
Medium / Depth-first search + parent links / interactiveCompare Two Sensor Trees
Compare two binary sensor trees in {"a":[...],"b":[...]}. Return true only when values and missing-child positions agree. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / Paired recursive traversal / interactiveMirror a Binary Sensor Rack
Swap every binary node’s left and right subtrees. Return the mirrored tree in indexed slot format. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / Recursive child swap / interactiveFind the Best Connected Sensor Route
A route may start and end at any nodes in a binary sensor tree but cannot branch or reuse a node. Return its maximum total reading. Empty input returns 0. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Hard / Postorder branch gains / interactiveShip and Restore a Sensor Tree
Encode a binary tree in preorder with explicit null markers, reconstruct fresh nodes, and return {"encoded":[...],"decoded":[...]}. The decoded tree uses the input slot format. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Hard / Preorder stream with null markers / interactiveLocate a Matching Sensor Branch
Given trees {"a":[...],"b":[...]}, return whether b exactly matches a complete subtree of a. An empty candidate is always a match. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / Traversal plus structural equality / interactiveRebuild a Rack from Two Visit Logs
Given distinct values in {"preorder":[...],"inorder":[...]}, reconstruct the binary tree and return indexed slots. Logs must describe the same tree. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / Inorder split with preorder cursor / interactiveAudit the Rack’s Search Ordering
Return whether every binary node is strictly larger than all values in its left subtree and strictly smaller than all values in its right subtree. Duplicate values are invalid. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / Inherited open bounds / interactiveSelect a Ranked Rack Reading
For a valid distinct-valued binary search tree, return the kth smallest reading. Parameter k is one-based and must identify an existing node. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / Iterative inorder stack / interactiveFind the Shared Rack Junction
Given {"tree":[...],"p":number,"q":number} for an ordered binary rack, return the deepest node whose subtree contains both readings. A node counts as its own descendant; both values must exist. Binary input arrays use heap-indexed slots: children of slot i are 2i+1 and 2i+2; null is an absent node.
Medium / BST split point / interactiveIndex Warehouse Code Prefixes
Run ["add",word], ["search",word] and ["prefix",prefix] operations on a lowercase-code trie. Return one result per operation: null for add, boolean for queries.
Medium / Prefix trie with terminal marker / interactiveQuery Code Patterns with Wildcards
Run ["add",word] and ["search",pattern] operations. A dot in a query matches exactly one lowercase letter. Return null for additions and booleans for searches.
Medium / Trie DFS at wildcard positions / interactiveFind a Dictionary on the Tile Board
Given {"board":[[letters]],"words":[...]}, return all listed words traceable through side-sharing tiles without reusing a tile in one route. Return unique found words alphabetically.
Hard / Trie-guided backtracking / interactiveWhere this leads
Keep following the branch when this pattern feels familiar.