parikshan

Trees

The core idea

A binary tree is a recursive shape: it is either empty, or it is a root with a left subtree and a right subtree. Most tree problems are solved by a recursion that matches that shape exactly. Write down what the function returns for an empty tree, then describe how the answer for a non-empty tree is built from the answers for its two children.

Three canonical recursions cover almost everything:

  1. Return a value: depth, sum, max, true / false. f(node) = combine(f(node.left), f(node.right), node.val).
  2. Return a value, with a side-effect on a global: diameter, longest path; the function returns a "downward" value and updates a separate "answer".
  3. BFS by level: a queue, processed in slices the size of the current level.

Binary search trees add the in-order invariant: left subtree < node < right subtree. That invariant lets you descend in O(log n) instead of O(n).

When to reach for it

Trigger phrases:

  • "binary tree" or "binary search tree" anywhere in the statement.
  • "depth", "height", "diameter", "path"
  • "validate", "invert", "mirror"
  • "level order", "zigzag"
  • "lowest common ancestor"

How to approach

  1. Decide which of the three recursions fits.
  2. Write the base case first: what does the function return for an empty tree?
  3. Write the recursive case: combine the children's answers with this node's value.
  4. If you find yourself wanting to pass information "down" the tree (e.g. bounds), add parameters. If you want to gather information "up", return tuples.

Iterative tree traversals exist (with an explicit stack) but should be a refactor of a recursive solution, not a first draft.

Real-world applications

  • File systems: directories form a tree; du, find, tar are tree traversals.
  • HTML / XML / DOM: layout engines walk the DOM tree thousands of times per second.
  • Decision trees in machine learning.
  • AST walkers in compilers, linters, code formatters.
  • Database indexes: B-trees are trees with high fanout.
  • Routing tables: tries are trees with characters as edge labels.
  • Game AI: minimax over game-state trees.

In the AI-integrated workspace

Agents are strong on recursive tree code because the recursion mirrors the data structure. The two bugs to watch for are:

  • Stack overflow on deep trees: the agent will not warn you. If the input is a tree of 10⁵ nodes shaped like a linked list, the recursion will blow the stack. For problems with this risk, the agent should reach for an explicit iterative traversal; if it does not, ask.
  • BST validation by checking neighbours: a common wrong answer is "left.val < node.val < right.val for every node". That is necessary but not sufficient (a subtree's grandchild can violate the global invariant). The correct check uses bounds passed down. Any "validate BST" code that does not pass (lo, hi) parameters is wrong.

When reading agent code for a tree problem, the cue for quality is whether the function name reads like an English sentence about the subtree. max_depth(node), is_balanced(node), sum_paths(node, remaining). Names that describe the subtree, not the procedure, mean the agent has seen the pattern. Names like solve or helper mean it hasn't.

Problems in this cluster

Easy: maximum-depth-of-binary-tree, invert-binary-tree, same-tree, symmetric-tree, balanced-binary-tree, diameter-of-binary-tree, path-sum. Medium: binary-tree-level-order-traversal, validate-bst, lowest-common-ancestor-bst.

Start with maximum-depth-of-binary-tree. It is the cleanest example of the "return a value" recursion.