☕ DSA Java Articles

Topics › Binary Trees › Traversals

Binary Tree Representation in Java

Easy TUF ID 2864 A2Z

Java source ↗ Edit this article ↗

What this covers

A binary tree is a picture of nodes and arrows until you decide how to store it. In Java the standard answer is a small node class with two references, but trees also arrive as arrays: LeetCode writes them in level order with null for missing children, and heaps live in an array with index arithmetic instead of references. Being fluent in all three forms, and in converting between them, is what lets you write tests for every tree problem that follows.

This article covers the node class, building a tree by hand, reading and writing the level-order format, the array layout with its index formulas, and comparing two trees for structural equality. All code is in the Java file and tested in main.

The node class

static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;                       // left and right start as null: a new node is a leaf
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

A node holds an int value and two references of its own type. That self-reference is what makes the structure recursive: left is not “a child value”, it is a whole tree (possibly empty). A few points that trip people up:

Building a tree by hand

The most direct way is to create the root and attach children one reference at a time. This builds:

      1
     / \
    2   3
     \
      5

static TreeNode buildByHand() {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.right = new TreeNode(5);        // 2 has no left child, so its left stays null
    return root;
}

root.left.right reads as “the right child of the left child of the root”. Every assignment like this is a pointer write; nothing is copied. Note that attaching 5 to root.left requires root.left to exist first, otherwise the expression throws NullPointerException.

The three-argument constructor builds the same tree as a single nested expression, whose indentation can mirror the picture. This style is convenient for small fixed trees in tests.

static TreeNode buildNested() {
    return new TreeNode(1,
            new TreeNode(2, null, new TreeNode(5)),
            new TreeNode(3));
}

Reading a tree from level order

LeetCode describes the tree above as [1, 2, 3, null, 5]. The rule: list the nodes level by level, left to right; for every real node, list its two children, writing null for a missing one; never list children of a null; drop trailing nulls.

To rebuild a tree from that list, keep a queue of nodes that are still waiting for their children. Each queued node consumes the next two entries of the array, one for its left child and one for its right child. Every real child is created and joins the back of the queue, because it will need its own children later.

static TreeNode fromLevelOrder(Integer... vals) {
    if (vals.length == 0 || vals[0] == null) return null;
    TreeNode root = new TreeNode(vals[0]);
    Queue<TreeNode> parents = new ArrayDeque<>();     // nodes still waiting for their children
    parents.offer(root);
    int i = 1;
    while (i < vals.length && !parents.isEmpty()) {
        TreeNode parent = parents.poll();
        if (vals[i] != null) {
            parent.left = new TreeNode(vals[i]);
            parents.offer(parent.left);
        }
        i++;
        if (i < vals.length && vals[i] != null) {
            parent.right = new TreeNode(vals[i]);
            parents.offer(parent.right);
        }
        i++;
    }
    return root;
}

Walking through [1, 2, 3, null, 5]:

Parent taken from queue Entries consumed Effect Queue after
(root created from entry 0) 1 root = 1 [1]
1 2, 3 1.left = 2, 1.right = 3 [2, 3]
2 null, 5 2.left stays null, 2.right = 5 [3, 5]

The array is exhausted, so nodes 3 and 5 keep null children. The method takes Integer... rather than int[] because it must be able to hold null, and the varargs form lets tests write fromLevelOrder(1, 2, 3, null, 5) directly.

Writing a tree back to level order

The inverse uses a breadth-first walk that, unlike an ordinary BFS, also enqueues missing children. A dequeued null is written to the output but contributes no children of its own, which matches the rule “never list children of a null”. The trailing nulls produced by the last level carry no information and are trimmed.

static List<Integer> toLevelOrder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();          // LinkedList, because ArrayDeque rejects null
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            out.add(null);                               // a missing child is written, its children are not
            continue;
        }
        out.add(node.val);
        queue.add(node.left);
        queue.add(node.right);
    }
    while (!out.isEmpty() && out.get(out.size() - 1) == null) out.remove(out.size() - 1);
    return out;
}

Two Java details matter here. ArrayDeque throws on null elements, so the queue is a LinkedList, which accepts them. And out.remove(out.size() - 1) calls remove(int index) because the argument is an int expression; out.remove(null) would instead call remove(Object) and delete the first null in the list.

Writing and reading are exact inverses on valid input, which the tests check with round trips on perfect, skewed, single-node and empty trees.

The array layout

A complete tree (all levels full except the last, which is filled from the left) can be stored in an array with no references at all. Number the positions level by level starting at 0. Then the node at index i has its children at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2. This is how binary heaps are stored.

static int leftIndex(int i) { return 2 * i + 1; }
static int rightIndex(int i) { return 2 * i + 2; }
static int parentIndex(int i) { return (i - 1) / 2; }

The parent formula relies on integer division: indices 5 and 6 both give parent 2. For index 0 it gives (0 - 1) / 2 = 0 in Java, because integer division truncates toward zero; the root has no parent, so callers must not ask.

Building a linked tree from this layout is a direct recursion on indices:

static TreeNode fromArray(Integer[] arr) {
    return fromArray(arr, 0);
}

private static TreeNode fromArray(Integer[] arr, int i) {
    if (i >= arr.length || arr[i] == null) return null;
    TreeNode node = new TreeNode(arr[i]);
    node.left = fromArray(arr, leftIndex(i));
    node.right = fromArray(arr, rightIndex(i));
    return node;
}

For complete trees the array layout and the level-order format are identical. They differ as soon as a node is missing: the array layout keeps the slots for that node’s (non-existent) children, while level order does not list them. Consider the right chain 1 -> 3 -> 7:

Format Contents
Level order [1, null, 3, null, 7]
Array layout [1, null, 3, null, null, null, 7]

In the array layout, 7 is the right child of 3 at index 2, so it must sit at index 2 * 2 + 2 = 6, and the slots 3, 4 and 5 under the missing left child of the root are wasted. On a skewed tree the waste is exponential: a chain of 30 nodes needs an array of about a billion slots. That is why the array layout is used only for (nearly) complete trees, and the reference-based node is the general representation.

Comparing two trees

Tests constantly need to ask “did I build the tree I expected?”. Two trees are the same when both are empty, or when both roots hold the same value and the left subtrees match and the right subtrees match.

static boolean sameTree(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && sameTree(a.left, b.left) && sameTree(a.right, b.right);
}

The first line handles all cases with a null: if either side is null, the trees match only if both are. This function also shows why left and right matter: [1, 2] (2 as left child) and [1, null, 2] (2 as right child) contain the same values but are different trees.

Which representation when

Representation Good for Weak at
Node objects with left and right any shape; inserting and removing subtrees no direct access by position; memory per node
Level-order list with nulls writing tests; reading problem input; serialisation must be decoded before use
Array with index arithmetic complete trees and heaps; cache-friendly; no references wastes space on sparse or skewed trees

Edge cases and pitfalls