Skip to content

Volume ITechnology

4.14.0 — Trees: The Pattern ​

Recognition cue. The input is a tree. The real question is always the same one:

What does this node do, and what does it need from its children?

Answer that and the code writes itself. Almost every problem here is a traversal with different work done at the node.

The two directions ​

This frame makes the whole chapter easier, so decide which direction the information flows before you write a single line.

Information flowing UP — return it. Depths, sums, counts, validity. The node cannot answer until its children have. This is post-order.

Information flowing DOWN — pass it as a parameter. The maximum seen on the path, an allowed range, the depth so far. Each branch gets its own copy, so no undo is needed.

Several problems do both: a range goes down, a count comes up.

The one structure that catches people ​

For the harder problems, what the function returns is not what the problem asks for.

  • Diameter returns the depth, records the best turning point.
  • Maximum Path Sum returns the best one-sided sum, records the best two-sided sum.

The reason is always the same: a parent can only extend a path through one child, but the answer is allowed to turn around and use both. Two different numbers, so one is returned and the other kept on the side.

Return what the parent needs; record what the question wants.

The three templates ​

python
# 1. DFS, information up (post-order)
def solve(node):  # (1)
    if not node: return base_value  # (2)
    left = solve(node.left)  # (3)
    right = solve(node.right)
    return combine(node.val, left, right)  # (4)

# 2. DFS, information down
def solve(node, state):  # (5)
    if not node: return
    new_state = update(state, node)  # (6)
    solve(node.left, new_state)  # (7)
    solve(node.right, new_state)

# 3. BFS, level by level
queue = deque([root])  # (8)
while queue:
    for _ in range(len(queue)):        # (9) ← freeze the level size FIRST
        node = queue.popleft()
        ...
        if node.left:  queue.append(node.left)  # (10)
        if node.right: queue.append(node.right)

The templates, line by line.

(1) Template 1 sends answers up the tree. (2) A missing node returns the simplest possible answer, such as 0 for a depth. (3) Ask both children first and trust their answers. (4) Build this node's answer from its own value and the two answers. Depth, diameter and balance all fit this shape.

(5) Template 2 sends information down, as an extra argument. (6) Fold this node into what was passed down, such as "the largest value on the path so far". (7) Hand the new information to both children. Each child gets its own copy, so the branches never interfere.

(8) Template 3 visits the tree level by level, using a queue that starts with the root. (9) Measure the queue before the inner loop. At that moment it holds exactly one level, so the inner loop handles exactly that level. (10) Queue the children, left before right. They belong to the next level and wait for the next turn.

DFS or BFS? ​

usewhenspace
DFSthe answer depends on subtrees — depth, sums, paths, validationO(h)
BFSthe answer depends on levels, or you want the shallowest and can stop earlyO(w)

On a balanced tree the last level holds about half the nodes, so BFS is O(n) and DFS is O(\log n). On a degenerate tree it reverses. Say "height", not "log n", unless balance is promised.

The fifteen problems ​

#ProblemThe one insight
4.14.1Invert Binary Tree ★Swap here, trust the recursion below
4.14.2Maximum Depth ★1 + max(left, right)
4.14.3DiameterReturn depth, record the turning point
4.14.4Balanced Binary TreeOne pass, -1 as the failure sentinel
4.14.5Same Tree ★Recurse on both trees at once
4.14.6Subtree of Another Tree ★Same Tree tried at every node
4.14.7LCA of a BST ★Walk to the split point; ordering replaces searching
4.14.8Level Order Traversal ★Freeze len(queue) to bound the level
4.14.9Right Side View ★The last node of each level
4.14.10Count Good NodesCarry the path maximum down
4.14.11Validate BST ★Carry a (low, high) range down — subtrees, not children
4.14.12Kth Smallest in a BST ★In-order gives sorted output; stop at k
4.14.13Construct from Preorder + Inorder ★Pre-order gives the root, in-order gives the split
4.14.14Maximum Path Sum ★Clamp negative branches to zero
4.14.15Serialize and Deserialize ★Null markers make one traversal enough

★ marks the Blind 75 subset.

The traps on this pattern ​

Validating a BST by comparing parent and child. The property is about entire subtrees. See the counterexample on 4.14.11.

Forgetting to freeze the level size in BFS. Children added mid-loop change len(queue) and the level boundary is lost.

Edges versus nodes. Diameter counts edges; depth counts nodes. They differ by one and the problem statement decides which.

Recomputing depth at every node. That is the O(n^2) trap in Balanced Binary Tree; compute each depth once on the way up.

Assuming O(\log n) space. It is O(h), and h is n on a degenerate tree.

Using pop(0) as a queue. O(n) in Python. Use collections.deque.

What the interviewer will push on ​

"Does information flow up or down here?" Say it before coding. It picks the template.

"Why does your function return something different from the answer?" The parent can only extend one side.

"Why is checking parent against child not enough for a BST?" The counterexample.

"How do you know where a BFS level ends?" The frozen length.

"Which uses more memory, DFS or BFS?" O(h) against O(w), and which is worse depends on the tree's shape.

One thing to volunteer: state the recursion in one English sentence before writing it. "The depth of a tree is one more than the depth of its deeper subtree." If you cannot produce that sentence, the code will not be right either.

Recall

  • The question is always what does this node do, and what does it need from its children.
  • Up = return value (post-order). Down = parameter. Many problems use both.
  • Hard problems return one thing and record another, because a parent can extend only one side while the answer may turn around and use both.
  • BFS levels need the queue length frozen before the inner loop.
  • In-order on a BST gives sorted output — that fact solves validation, k-th smallest, and range queries.
  • Validate a BST with a (low, high) range carried down. Comparing parent to child is the classic wrong answer.
  • Space is O(h) for DFS and O(w) for BFS; on a balanced tree that is O(\log n) against O(n).
  • One traversal plus null markers determines a tree; without markers you need two traversals.

Next: 4.14.1 Invert Binary Tree — the simplest possible version of "do something here, then recurse".

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet