Binary Tree Problems in Java: Traversals, Height, and the One Recursive Template Interviews Keep Testing

Binary tree questions can look like a long list of unrelated problems. In practice, most of them use the same recursive shape, with only the combine step changing. Once you can trace four traversals and settle the height convention, diameter, balance, and node counts become much less intimidating.

The Java Node and the recursive template

A binary-tree node stores a value and at most two references:

class Node {
    int val;
    Node left;
    Node right;

    Node(int val) {
        this.val = val;
    }
}

Most depth-first tree methods then follow four moves:

1. Handle the null base case.

2. Recurse into the left subtree.

3. Recurse into the right subtree.

4. Combine the two answers with the current node.

For a traversal, combining may mean printing a value. For height, it means taking a maximum. For node count, it means adding one. For diameter, it means testing whether the longest path passes through the current node.

Depth-first traversals use recursion or an explicit stack. Level-order traversal is breadth-first, so it uses a queue. Keeping those two families separate prevents many implementation mistakes.

Building the six-node binary tree in Java

Node 1 is the root. Its children are 2 and 3. Node 2 has children 4 and 5. Node 3 has no left child and has 6 as its right child.

Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);

There are six nodes and five parent-child edges. Node 3 having only a right child is the asymmetry that punishes code without a null check. It does not disturb the heights, because node 6 sits at the same depth as nodes 4 and 5, so both subtrees under the root are still one edge tall. Traversal orders and heights belong to this exact shape, so moving a single edge changes the answers.

Four binary-tree traversals, worked exactly

The three depth-first orders differ only in when the current node is visited.

• Preorder, root-left-right: visit 1, complete the subtree rooted at 2, then complete the subtree rooted at 3. The order is 1, 2, 4, 5, 3, 6.

• Inorder, left-root-right: complete the left subtree, visit the root, then complete the right subtree. The order is 4, 2, 5, 1, 3, 6.

• Postorder, left-right-root: complete both subtrees before visiting their root. The order is 4, 5, 2, 6, 3, 1.

• Level-order, breadth-first: visit nodes level by level. The order is 1, 2, 3, 4, 5, 6.

Recursive preorder is the template with the visit placed first. Moving visit(node.val) between the two recursive calls produces inorder. Moving it after both calls produces postorder.

void preorder(Node node) {
    if (node == null) return;
    visit(node.val);
    preorder(node.left);
    preorder(node.right);
}

For level-order, enqueue 1. Dequeue and visit it, then enqueue 2 and 3. Dequeue 2 and enqueue 4 and 5; dequeue 3 and enqueue only 6. The queue therefore exposes the nodes in the order 1, then 2, 3, then 4, 5, 6.

The queue version is not the template with the visit line moved. It drops the recursion and lets the queue hold the frontier:

void levelOrder(Node root) {
    if (root == null) return;
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        visit(node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

Binary-tree height without the off-by-one fight

Height questions become safe once you state the convention before calculating. This version counts edges on the longest downward path:

int height(Node node) {
    if (node == null) return -1;
    return 1 + Math.max(height(node.left), height(node.right));
}

The -1 base value makes a leaf's height zero. Now calculate from the bottom:

• height(4) = 1 + max(-1, -1) = 0.

• height(5) = 0, so height(2) = 1 + max(0, 0) = 1.

• height(6) = 0, so height(3) = 1 + max(-1, 0) = 1.

• height(1) = 1 + max(1, 1) = 2.

The tree's edge-based height is 2. If a question defines height as the number of nodes on the longest path, the same path contains three nodes, so the answer is 3. Neither convention is wrong. The mistake is using one convention in the base case and the other in the final answer.

Reusing the template for tree diameter and node count

The diameter is the longest path between any two nodes. With edge-based heights, a path that passes through a node has this length:

height(left) + height(right) + 2

At root 1, the left subtree rooted at 2 has height 1 and the right subtree rooted at 3 also has height 1. The candidate diameter is therefore 1 + 1 + 2 = 4 edges.

That value corresponds to the path 4 -> 2 -> 1 -> 3 -> 6. It contains five nodes and four edges. No candidate lower in the tree is longer, so the tree's diameter is 4 edges.

An efficient method returns height as it unwinds and updates a running best diameter at each node. It is the height template with one extra comparison, not an entirely new idea.

Node counting reuses the same shape with a different base value and a different combine step:

int count(Node node) {
    if (node == null) return 0;
    return 1 + count(node.left) + count(node.right);
}

Each leaf returns 1 + 0 + 0 = 1, so count(4), count(5) and count(6) are all 1. That gives count(2) = 1 + 1 + 1 = 3 and count(3) = 1 + 0 + 1 = 2, because node 3 contributes nothing on the left. At the root, count(1) = 1 + 3 + 2 = 6, which matches the six nodes in the tree.

Balance is the same template once more. A tree is height-balanced when no node's two subtree heights differ by more than one, so compare the heights already calculated: node 2 has 0 and 0, node 3 has -1 and 0, and node 1 has 1 and 1. The largest gap anywhere is 1, at node 3, so this tree is height-balanced. Leaf counts and subtree sums come from the same three decisions: the base value, what each call returns, and the combine step.

Binary-tree traps that cost the mark

Small assumptions cause most wrong answers:

• Mixing edge height and node height: state the convention and choose the matching base case.

• Assuming every node has two children: node 3 proves why every method needs a null check.

• Using plain recursion for level-order: the call stack naturally follows depth; a queue preserves breadth.

• Confusing height with depth: height goes down from a node to its deepest leaf; depth goes down from the root to that node.

• Ignoring a skewed tree: a very deep recursive call chain can throw StackOverflowError. An iterative stack-based version is the practical alternative when depth is unsafe.

If the tree is specifically a search tree, ordering adds another layer: every key in a node's left subtree is smaller than that node and every key in its right subtree is larger, which is why an inorder traversal of a search tree comes out sorted. None of the methods above ever compares two values, so they run on any binary tree, ordered or not. The binary trees and binary search trees guide takes that ordering rule further, into search, insert and delete.

How interviews frame binary-tree problems

A direct prompt may ask you to write preorder, compute height, or print nodes level by level. A template check may ask for diameter, leaf count, balance, or the number of nodes in a subtree. In each case, identify the base value, decide what each recursive call returns, and define the combine step before writing code.

KnowledgeGate's question bank has over 1,500 data-structures questions, covering binary trees and BSTs. Use the data structures trees MCQ set to practise tracing, not just reading code. The wider Coding & DSA collection helps place these tree patterns beside the other structures used in placement rounds.

The short version and your next step

Learn one null-safe recursion template. Produce preorder, inorder, postorder, and level-order for a drawn tree without guessing. Fix the height convention before calculating, then reuse height results to compute diameter.

Your next step is to implement the four traversals, height, and diameter for this six-node example in the DSA using Java course. Change one edge, calculate the new answers on paper, and only then run the code. That comparison is what makes the template stick.