Binary Trees Aren't Hard. These Six Bugs Are.

You can solve 50 LeetCode problems on arrays and linked lists and feel pretty good about yourself. Then a binary tree problem shows up. The recursion gets slightly weird. Your code passes six of seven test cases. You submit. Wrong Answer. Again.

These binary tree bugs cluster. The same six mistakes show up across thousands of candidates because binary trees have a specific shape of wrongness that isn't obvious until you've been burned by it. Every section below shows the wrong version first. You have been warned.

Your is_valid_bst at 2 AM versus the same code when the hidden test cases run

Your is_valid_bst at 2 AM versus your is_valid_bst when the judge runs the hidden tests.

The BST Validation Bug Everyone Writes First

Ask someone to validate a BST and they'll write this:

def is_valid_bst(node):
    if not node:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_valid_bst(node.left) and is_valid_bst(node.right)

It passes simple tests. That's what makes it dangerous. It fails on this tree:

Node 6 is a left child of 15, so 6 < 15 checks out locally. But 6 sits in the right subtree of the root, and 6 < 10 violates the BST property. The code above never catches it because it only looks one level at a time.

BST constraints are transitive: every node must be bounded by every ancestor, not just its direct parent. Going left tightens the upper bound. Going right tightens the lower bound. The fix is range propagation:

def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
    if not node:
        return True
    if not (min_val < node.val < max_val):
        return False
    return (is_valid_bst(node.left, min_val, node.val) and
            is_valid_bst(node.right, node.val, max_val))

One more thing. If your BST allows duplicate values, the comparison becomes min_val <= node.val < max_val or min_val < node.val <= max_val depending on which side duplicates live. Pick the wrong one and your validator rejects valid trees. Always clarify whether duplicates are allowed before you write a line.

Height vs. Depth: The Off-by-One That Breaks Things

These two words sound interchangeable. They're not, and mixing them up is one of the most common things candidates say wrong when explaining their code out loud.

Depth is measured top-down from the root. Height is measured bottom-up from the leaves. The root has depth 0. A leaf has height 0. They point in opposite directions.

The off-by-one creeps into the base case:

# Wrong
def height(node):
    if not node:
        return 0   # leaf returns 1, not 0

# Correct
def height(node):
    if not node:
        return -1  # null returns -1 so leaf returns 0
    return 1 + max(height(node.left), height(node.right))

When null returns 0, a leaf computes 1 + max(0, 0) = 1. That's a node count, not an edge count. Every height value shifts by one, quietly, forever. In an AVL tree or any balancing algorithm, a shift of one in the height definition means balance factors of ±2 on a perfectly balanced tree. One engineering team traced a production cache degrading from 50µs lookups to over 2 seconds because of exactly this. The kind of bug that sits in a codebase for months, disguised as a "mystery slowdown."

The sanity check: depth + height = tree height. If that identity holds for any node you pick, your definitions are consistent.

The Missing Return That Swallows Your Answer

This one costs time because the code looks correct on first read. Python is very helpful here. It will silently discard your answer for you.

# Wrong: recursive calls without return
def find_node(node, target):
    if not node:
        return None
    if node.val == target:
        return node
    if target < node.val:
        find_node(node.left, target)   # result silently discarded
    else:
        find_node(node.right, target)  # result silently discarded

# Correct
def find_node(node, target):
    if not node:
        return None
    if node.val == target:
        return node
    if target < node.val:
        return find_node(node.left, target)
    else:
        return find_node(node.right, target)

Without the return keyword, Python evaluates the recursive call and throws the result away. The function returns None to its caller instead of propagating the found node upward through the call stack. Everything looks fine until you test a target in the right subtree.

The same bug appears in any "search and return a reference" problem: lowest common ancestor, find path, find kth smallest. One missing return on a recursive branch and half your tree is unreachable.

Your Backtracking Doesn't Actually Backtrack

Path-collection problems need backtracking. Most candidates know this conceptually. A meaningful number forget to implement it.

The gap between "I know about backtracking" and "my backtracking works" is surprisingly wide.

# Wrong: path leaks across branches
def find_paths(node, target, path, result):
    if not node:
        return
    path.append(node.val)
    if not node.left and not node.right and sum(path) == target:
        result.append(path[:])
    find_paths(node.left, target, path, result)
    find_paths(node.right, target, path, result)
    # Missing: path.pop()

# Correct
def find_paths(node, target, path, result):
    if not node:
        return
    path.append(node.val)
    if not node.left and not node.right and sum(path) == target:
        result.append(path[:])
    find_paths(node.left, target, path, result)
    find_paths(node.right, target, path, result)
    path.pop()  # restore state before returning to parent

When you return from a node, you must undo what you added. Without path.pop(), the right subtree's DFS starts with the entire left subtree's path still in the list. Results look plausible. They're wrong.

The copy matters too. result.append(path) stores a reference to the same list object you keep mutating. Every path in your result points to the same empty list at the end. Always append a copy with path[:].

One Function, Two Jobs

The diameter of a binary tree is the longest path between any two nodes. Many candidates write a clean-looking function that gets the right answer but runs in O(n²):

# Correct answer, wrong complexity: recomputes height for every node → O(n²)
def diameter(node):
    if not node:
        return 0
    left_h = height(node.left)
    right_h = height(node.right)
    through_root = left_h + right_h
    left_dia = diameter(node.left)
    right_dia = diameter(node.right)
    return max(through_root, left_dia, right_dia)

height() reruns a full subtree traversal at every node. The correct answer, delivered slowly. In an interview, slow-and-correct is fine to start with, but you need to notice the redundancy and fix it.

The fix makes one function return height to the parent while updating a global maximum diameter on the side.

def diameter_of_binary_tree(root):
    max_diameter = [0]

    def height(node):
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        max_diameter[0] = max(max_diameter[0], left + right)
        return 1 + max(left, right)

    height(root)
    return max_diameter[0]

The pattern generalizes: whenever a problem asks for a whole-tree property but your recursion naturally computes a local value per node, return the local value upward and accumulate the global answer in an outer variable. Binary Tree Maximum Path Sum uses the exact same structure.

Don't Initialize to Zero

Maximum Path Sum specifies the path must include at least one node. Most candidates initialize their global maximum to 0:

# Wrong: fails on all-negative trees
def max_path_sum(root):
    max_sum = [0]  # should be float('-inf')

    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        max_sum[0] = max(max_sum[0], node.val + left + right)
        return node.val + max(left, right)

    dfs(root)
    return max_sum[0]

For a tree containing only [-3, -2, -1], the answer is -1. With max_sum = 0, the code returns 0 because 0 > -1. No path in the tree has sum zero, but the code claims one does.

Initialize to float('-inf'), not zero, whenever the problem requires at least one node. Zero works only when non-negative values are guaranteed. Interview trees contain negatives specifically to catch this. That's the whole point of the negative test case: it's not there to be mean, it's there to find out if your initialization logic actually makes sense.

Where Does One Level End?

Level order traversal: return the nodes of each level in their own list. The wrong approach reads nodes from the queue one at a time without fixing the level boundary:

# Wrong: children added mid-loop pollute the current level
def level_order(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    current_level = []
    while queue:
        node = queue.popleft()
        current_level.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    result.append(current_level)
    return result

This lumps every node into a single level and then stops. It looks almost right until you check the output. Snapshot the queue size before processing each level, then consume exactly that many nodes.

def level_order(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)  # freeze the boundary
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

The boundary-freeze technique handles right side view, zigzag traversal, and average of levels without any structural changes. Get this one right and a whole family of BFS tree problems becomes the same template.

The Six Binary Tree Bugs

Reading about mistakes isn't the same as catching them under pressure. Most of these are invisible until you run a test case that specifically targets the bug: an all-negative tree, a skewed tree where the diameter runs through one side only, a BST where a deep node violates the global constraint while passing every local check. If you want to practice catching these in a setting that feels like a real interview, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly this: do you test edge cases, do you catch the bug yourself, do you explain the fix clearly.

BST validation: check against the full ancestor range, not just the parent. Pass (min_val, max_val) bounds recursively.
Height vs. depth: null returns -1 so leaves correctly have height 0. Height is bottom-up, depth is top-down.
Missing return: every branch of a recursive search must return the recursive call, or None propagates silently.
Backtracking: always pop() after recursing. Always append(path[:]), not append(path).
Diameter pattern: return height locally, accumulate the global maximum in an outer variable.
Max path sum: initialize to float('-inf'), not 0, when the path must contain at least one node.
BFS level grouping: snapshot len(queue) before the inner loop so children added mid-loop don't contaminate the current level.