Binary Tree Patterns — Traversals, Recursion Template and BST Rules

Q: Which tree traversal should I use?

Inorder for a BST, because it yields values in sorted order. Postorder when a node's answer depends on its children — heights, deletions, bottom-up aggregation. Preorder for copying or serialising, since the root arrives first. Level order (BFS) for anything phrased per level.

Q: How do you validate a binary search tree?

Pass a valid range down the recursion: the left subtree inherits an upper bound of the current node's value, the right subtree a lower bound. Checking only that each node sits between its immediate children is the classic wrong answer — it accepts trees where a deep descendant violates the ordering against an ancestor.

Q: Why does the diameter problem return a different value than it records?

Because a path through a node — left depth plus right depth — cannot be extended further up the tree, while the value the parent needs is the longest path going straight down. So the recursion returns 1 + max(left, right) and separately records left + right in an enclosing variable as the running answer.

Trees are the largest section on the sheet — 32 problems — because almost every one is the same recursion wearing a different question. Get the template and the traversal orders solid and the section collapses into a handful of ideas.

The traversals

def inorder(node):
    if not node:
        return
    inorder(node.left)
    visit(node)              # preorder puts this first, postorder last
    inorder(node.right)

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    visit(node);             // preorder puts this first, postorder last
    inorder(node.right);
}

void inorder(TreeNode* node) {
    if (!node) return;
    inorder(node->left);
    visit(node);             // preorder puts this first, postorder last
    inorder(node->right);
}

void inorder(struct TreeNode* node) {
    if (!node) return;
    inorder(node->left);
    visit(node);             /* preorder puts this first, postorder last */
    inorder(node->right);
}

function inorder(node) {
  if (!node) return;
  inorder(node.left);
  visit(node);               // preorder puts this first, postorder last
  inorder(node.right);
}

The name says where the visit happens relative to the recursive calls. What matters is which one each question needs:

The name says where the node is visited relative to its children. Inorder on a BST yields sorted order — the most useful tree fact in interviews.

Order	Sequence	Use it for
Preorder	node, left, right	Copying/serialising a tree — the root arrives first
Inorder	left, node, right	BSTs — this yields sorted order
Postorder	left, right, node	Anything needing children's results first: height, deletion
Level order	breadth-first	Anything per level — see BFS

"Inorder on a BST is sorted" is the single most useful tree fact in interviews. It answers

Validate BST, Kth Smallest in a BST and BST Iterator directly.

The recursion template

Nearly every tree problem fits this shape: handle the empty node, recurse both ways, combine.

def solve(node):
    if not node:
        return base_case          # 0, None, True — whatever the identity is
    left = solve(node.left)
    right = solve(node.right)
    return combine(node.val, left, right)

T solve(TreeNode node) {
    if (node == null) return baseCase;   // the IDENTITY for whatever you combine:
                                         // 0 for a sum, true for an AND,
                                         // MIN_VALUE for a maximum
    T left = solve(node.left);
    T right = solve(node.right);
    return combine(node.val, left, right);
}

T solve(TreeNode* node) {
    if (!node) return baseCase;   // the IDENTITY for whatever you combine
    T left = solve(node->left);
    T right = solve(node->right);
    return combine(node->val, left, right);
}

function solve(node) {
  if (!node) return baseCase;    // the IDENTITY for whatever you combine:
                                 // 0 for a sum, true for an AND, -Infinity for max
  const left = solve(node.left);
  const right = solve(node.right);
  return combine(node.val, left, right);
}

def max_depth(node):
    if not node:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

int maxDepth(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

int maxDepth(TreeNode* node) {
    if (!node) return 0;
    return 1 + max(maxDepth(node->left), maxDepth(node->right));
}

int maxDepth(struct TreeNode* node) {
    if (!node) return 0;
    int l = maxDepth(node->left), r = maxDepth(node->right);
    return 1 + (l > r ? l : r);
}

function maxDepth(node) {
  if (!node) return 0;
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

Getting the base case right is the problem most of the time. It is the identity element for whatever you are combining: 0 for a sum or depth, True for a universal check, -inf for a maximum.

Return one thing, track another

The trick behind every "path" problem, and the thing that separates a clean solution from a tangle. Some questions need the recursion to return one value while the answer is a different value computed at each node. Keep the answer in an enclosing variable.

def diameter_of_binary_tree(root):
    best = 0

    def depth(node):
        nonlocal best
        if not node:
            return 0
        left, right = depth(node.left), depth(node.right)
        best = max(best, left + right)      # the answer: a path THROUGH this node
        return 1 + max(left, right)         # the return: a path DOWN from this node

    depth(root)
    return best

private int best;

int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    depth(root);
    return best;
}

private int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left), right = depth(node.right);
    best = Math.max(best, left + right);   // the ANSWER: a path THROUGH this node
    return 1 + Math.max(left, right);      // the RETURN: a path DOWN from it
}

int depth(TreeNode* node, int& best) {
    if (!node) return 0;
    int left = depth(node->left, best), right = depth(node->right, best);
    best = max(best, left + right);   // the ANSWER: a path THROUGH this node
    return 1 + max(left, right);      // the RETURN: a path DOWN from it
}

int diameterOfBinaryTree(TreeNode* root) {
    int best = 0;
    depth(root, best);
    return best;
}

static int depth(struct TreeNode* node, int* best) {
    if (!node) return 0;
    int left = depth(node->left, best), right = depth(node->right, best);
    if (left + right > *best) *best = left + right;   /* path THROUGH */
    return 1 + (left > right ? left : right);          /* path DOWN */
}

int diameterOfBinaryTree(struct TreeNode* root) {
    int best = 0;
    depth(root, &best);
    return best;
}

function diameterOfBinaryTree(root) {
  let best = 0;

  const depth = (node) => {
    if (!node) return 0;
    const left = depth(node.left), right = depth(node.right);
    best = Math.max(best, left + right);   // the ANSWER: a path THROUGH this node
    return 1 + Math.max(left, right);      // the RETURN: a path DOWN from it
  };

  depth(root);
  return best;
}

Binary Tree Maximum Path Sum is the same skeleton with one addition — clamp negative

subtree contributions to zero with max(0, …), since a negative branch is never worth including.

Lowest common ancestor

Elegant enough to be worth memorising. Return the node if it is either target; otherwise recurse both sides. If both sides return something, this node is the LCA; if only one does, pass it up.

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;   // targets split here
    return left != null ? left : right;               // pass the found one up
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left && right) return root;    // targets split here
    return left ? left : right;        // pass the found one up
}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root,
                                      struct TreeNode* p,
                                      struct TreeNode* q) {
    if (!root || root == p || root == q) return root;

    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left && right) return root;    /* targets split here */
    return left ? left : right;
}

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;   // targets split here
  return left || right;             // pass the found one up
}

On a BST it is simpler still: walk down while both targets are on the same side, and the first node that splits them is the answer — O(height), no recursion needed.

Validating a BST

The classic wrong answer checks left.val < node.val < right.val locally. That passes a tree where a deep left descendant is larger than the root. The BST property is about

ranges, not neighbours, so pass bounds down:

def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    if not node:
        return True
    if not low < node.val < high:
        return False
    return (is_valid_bst(node.left, low, node.val)
            and is_valid_bst(node.right, node.val, high))

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

/** Longs, not ints — a node holding Integer.MIN_VALUE is legal and would
    fail against an int sentinel. */
private boolean validate(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return validate(node.left, low, node.val)
        && validate(node.right, node.val, high);
}

bool validate(TreeNode* node, long low, long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return validate(node->left, low, node->val)
        && validate(node->right, node->val, high);
}

bool isValidBST(TreeNode* root) {
    // longs, not ints — a node holding INT_MIN is legal
    return validate(root, LONG_MIN, LONG_MAX);
}

static bool validate(struct TreeNode* node, long low, long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return validate(node->left, low, node->val)
        && validate(node->right, node->val, high);
}

bool isValidBST(struct TreeNode* root) {
    return validate(root, LONG_MIN, LONG_MAX);
}

function isValidBST(node, low = -Infinity, high = Infinity) {
  if (!node) return true;
  // The bounds are INHERITED, not checked against immediate children —
  // that is what catches a deep descendant violating an ancestor.
  if (node.val <= low || node.val >= high) return false;
  return isValidBST(node.left, low, node.val)
      && isValidBST(node.right, node.val, high);
}

The alternative — inorder traverse and check the sequence is strictly increasing — is equally valid and often easier to explain.

Construction and serialisation

Construct from Preorder and Inorder rests on one observation: preorder's first element is

the root, and finding it in the inorder list splits that list into the left and right subtrees. Build a value → index map for the inorder array first, or the repeated linear search makes it O(n²).

Serialize and Deserialize is preorder with explicit null markers. Nulls are what make the

string unambiguous — without them a single traversal cannot reconstruct the shape.

Complexity

O(n) time for a full traversal. Space is O(h) for the recursion stack: O(log n) on a balanced tree, O(n) on a degenerate one — which is why "what if the tree is a linked list" is a fair follow-up. Morris traversal achieves O(1) space by temporarily rewiring pointers, and is worth knowing exists.

Mistakes that cost the round

Checking the BST property locally instead of with inherited bounds.
Confusing the answer with the return value in path problems — a path through a node

cannot be extended upward, only a path down can.

Wrong base case. return 0 where the identity should be -inf breaks maximum

problems on all-negative trees.

Missing null markers when serialising.
Ignoring stack depth on a skewed tree.

What to drill

Start with the easy tier — Maximum Depth, Invert, Symmetric, Same Tree — until the template is automatic, then:

Diameter of Binary Tree — return one thing, track another.
Validate Binary Search Tree — the bounds argument.
Lowest Common Ancestor — both the general and BST versions.
Construct Binary Tree from Preorder and Inorder — the split insight.
Serialize and Deserialize Binary Tree — null markers.
Binary Tree Maximum Path Sum — the Hard version of the diameter trick.

All 32 are on the 22 DSA Patterns sheet.

Frequently asked

Which tree traversal should I use?

Inorder for a BST, because it yields values in sorted order. Postorder when a node's answer depends on its children — heights, deletions, bottom-up aggregation. Preorder for copying or serialising, since the root arrives first. Level order (BFS) for anything phrased per level.

How do you validate a binary search tree?

Pass a valid range down the recursion: the left subtree inherits an upper bound of the current node's value, the right subtree a lower bound. Checking only that each node sits between its immediate children is the classic wrong answer — it accepts trees where a deep descendant violates the ordering against an ancestor.

Why does the diameter problem return a different value than it records?

Because a path through a node — left depth plus right depth — cannot be extended further up the tree, while the value the parent needs is the longest path going straight down. So the recursion returns 1 + max(left, right) and separately records left + right in an enclosing variable as the running answer.

Trees