What Is a Binary Tree? The Concept Behind Every Tree Interview

Every technical interview that touches data structures will eventually arrive at a tree. Not because the interviewer loves nature, but because heaps, BSTs, expression parsers, and about forty LeetCode problems all sit on top of this one structure. Once you can reason about binary trees fluently, a large class of hard-looking problems collapses into the same three questions wearing different hats.

A Binary Tree Is Just a Node With Two Pointers

A binary tree is a collection of nodes where each node holds a value, a pointer to a left child, and a pointer to a right child. Either pointer can be null. That's the entire definition. You've already heard the hard part.

Every LeetCode tree problem uses this exact structure:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(
        val = 0,
        left: TreeNode | null = null,
        right: TreeNode | null = null
    ) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

The class is identical across Java, C++, Go, and everything else. Universally three fields. If you've used a linked list, this feels familiar. A linked list node is a value plus one next pointer. A tree node is a value plus two child pointers. The branching is the only difference, and it changes everything about how you traverse and reason about the structure.

Seven Nodes, Four Terms You'll Actually Need

A few terms that come up constantly:

Root: node 1 in the diagram above. It has no parent. Every tree has exactly one root. If it had two, it'd be a graph with ideas above its station.

Leaf: nodes 4, 5, 6, 7. Both child pointers are null. The ends of every branch, the nodes that gave up on growing.

Height: the number of edges on the longest path from the root to any leaf. This tree has height 2. A single-node tree has height 0 and a quiet dignity about it.

Depth: edges from the root down to a specific node. The root sits at depth 0. Every subtree is itself a valid binary tree, which is why recursive solutions click so naturally on tree problems.

"Binary" Is Not a Suggestion

The binary part means at most two children per node. Not exactly two. Not "a reasonable number." Not "three if you're running short on time." A node with three children is a general tree or n-ary tree. It just doesn't get to call itself binary.

Because every node branches into at most two paths, you can reason about height and write recursive algorithms with confidence. A tree with n nodes has exactly n - 1 edges. Every node except the root has exactly one parent. The structure is predictable in a way that makes your algorithm's behavior predictable too.

Not All Binary Trees Are the Same Shape

Interviewers use specific vocabulary. Learn these variants before you need to fake knowing them mid-interview:

Full binary tree: every node has either 0 or 2 children. No node has exactly one child. Every branch commits.

Complete binary tree: all levels fully filled except possibly the last, which fills left to right. The heap is always a complete binary tree. This property is why heaps work efficiently as arrays.

Perfect binary tree: all interior nodes have two children and every leaf sits at the same depth. A perfect tree of height h has exactly 2^(h+1) - 1 nodes. Looks great on slides, almost never occurs in the wild.

Balanced binary tree: loosely, height is O(log n). The AVL definition makes it precise: the height difference between left and right subtrees of every node is at most 1.

Binary search tree (BST): a binary tree with an ordering property. For every node, all values in its left subtree are smaller and all values in its right subtree are larger. The BST invariant is what makes efficient search possible, not the tree shape alone.

Height Controls Everything

Read this section twice.

The height of the tree determines how long every traversal path takes. This is the single most important fact about binary tree complexity.

A perfectly balanced tree with n nodes has height O(log n). Each level roughly doubles the node count: 1, 2, 4, 8... By the time you've stacked up n nodes, you've only used log₂(n) levels.

A degenerate tree is a different story. When every node has exactly one child, the structure stretches into a straight line. It looks, walks, and performs like a linked list that is very confused about what kind of data structure it is. Height is O(n). The same BST algorithm that takes O(log n) on a balanced tree now takes O(n) on this guy. This is why balancing matters, and why interviewers ask what happens when a BST becomes unbalanced.

Four Traversals, Four Different Jobs

There are four standard traversals. Each visits every node exactly once, so all cost O(n) time and O(h) space. The call stack goes as deep as the tree is tall.

Inorder (left, root, right): for a BST, this visits nodes in sorted ascending order. Whenever you need values in sequence, this is your traversal.

Preorder (root, left, right): visits the root before its subtrees. Useful for copying a tree or serializing it, because you always see a parent before its children.

Postorder (left, right, root): visits the root after both subtrees. Use this when children need to be processed before their parent: expression tree evaluation, subtree size computation, freeing memory.

Level-order (BFS): visits nodes level by level, left to right. Requires a queue. Use this for minimum depth, a row-by-row view, or anything that depends on horizontal structure.

The recursive implementations of the first three share one skeleton:

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val)     # move above left call → preorder
    inorder(root.right) # move below right call → postorder

Moving the print call before or after the recursive calls gives you the other two traversals. Three traversals, one skeleton, two print positions. This is either the most elegant thing in CS or a trick that someone is very pleased with themselves for noticing. Possibly both.

All four traversals have the same asymptotic cost. The order they visit nodes is what changes, and that order determines what problems they're useful for.

What Every Operation Actually Costs

Operation	Balanced tree	Skewed tree
Traversal	O(n)	O(n)
BST search	O(log n)	O(n)
BST insert	O(log n)	O(n)
BST delete	O(log n)	O(n)
Space (call stack)	O(log n)	O(n)

A plain binary tree without the BST property does not support efficient search. Without an ordering constraint, finding a value means checking every node: O(n). The tree structure alone doesn't buy you fast lookup. The BST invariant does. Surprisingly many candidates assume that tree shape equals BST behavior. It does not. This misunderstanding shows up in interviews, in code reviews, and in bug reports from production systems that should know better.

What Interview Problems Actually Test

The binary tree problems that cover every interview pattern fall into a few recurring families:

Path problems: maximum path sum, diameter, path sum to a target. You need DFS and a result value that updates as the recursion unwinds upward. The tricky bit is passing information back up through return values.

Structural problems: check symmetry, verify two trees are identical, check if one tree is a subtree of another. Mostly recursive comparisons that feel simple and have a surprisingly large number of edge cases.

BST problems: validate a BST, find the k-th smallest element, recover a swapped BST. All of these lean on the inorder traversal property. If you know that inorder on a BST gives sorted output, a large class of BST problems becomes much less mysterious.

Construction problems: build a tree from preorder and inorder traversal, or from level-order. These test whether you understand what information each traversal encodes. They're harder than they look because you have to think about what each traversal sequence uniquely determines.

Lowest common ancestor: given two nodes, find their closest shared ancestor. Shows up at Google, Meta, and Amazon. There's a clean recursive solution once you see the right framing.

The pattern across all of them: define what your function returns, recurse on both subtrees, combine the results. The most common mistake is tracking too much state in function parameters instead of letting return values carry information upward. If your solve function has five parameters, you've probably made this mistake.

The Recursive Shape of Every Tree Problem

Binary trees are the canonical recursion example because of self-similarity. Every subtree is itself a binary tree. The left child of the root is the root of its own binary tree. You can't look at a tree node without seeing a smaller version of the same problem staring back at you. Recursion isn't just one approach to tree problems. It's the shape of the problem.

Most tree problems share this skeleton:

def solve(root):
    if not root:
        return base_case

    left_result = solve(root.left)
    right_result = solve(root.right)

    return combine(left_result, right_result, root.val)

The base case handles None. The recursive calls collect results from both subtrees. The combine step produces the answer for the current node and passes it up. Recursion time complexity on a balanced binary tree follows T(n) = 2T(n/2) + O(1), which the Master Theorem resolves to O(n).

Space complexity is O(h) for the call stack. O(log n) on balanced, O(n) on skewed. When the tree could be degenerate and stack space matters, iterative DFS with an explicit stack sidesteps the risk at the cost of writing more code and managing a stack yourself.

When you're ready to explain this reasoning out loud under time pressure instead of just understanding it silently, SpaceComplexity runs voice-based mock interviews on tree problems with the same follow-up questions you'd get from a real interviewer at Google or Meta.

Key Takeaways

• A binary tree is a set of nodes where each node has at most two children (left and right)
• Root: no parent. Leaf: no children. Height: longest root-to-leaf path
• Height is O(log n) on a balanced tree and O(n) on a degenerate one. Same algorithm, very different performance
• All traversals cost O(n) time and O(h) space. Which one you pick depends on what order you need
• A binary tree alone does not support efficient search. The BST ordering property does. These are different things
• Most tree interview problems follow the same recursive shape: base case, recurse left, recurse right, combine

Further Reading

• Binary tree (Wikipedia)
• Binary search tree (Wikipedia)
• Tree traversal (Wikipedia)
• Binary Tree on GeeksforGeeks
• LeetCode Tree problem tag