Solving the Height of a Binary Tree Puzzle

You get an array like [1, 2, 3, 4, -1, -1, -1]. It represents a binary tree. -1 means null. Find the height.

The height of a tree is the number of edges on the longest path from root to leaf. A single node has height 0. An empty tree has height -1.

The intuition

First, build the tree from the array. The array uses level-order indexing: for a node at index i, its left child is at 2i + 1 and right child at 2i + 2. Then find the height recursively — it's the max height of the two subtrees, plus one.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function buildTree(arr, index = 0) {
    if (index >= arr.length || arr[index] === -1) {
        return null;
    }

    const node = new Node(arr[index]);
    node.left = buildTree(arr, 2 * index + 1);
    node.right = buildTree(arr, 2 * index + 2);
    return node;
}

function getHeight(node) {
    if (node === null) return 0;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

const tree = buildTree([1, 2, 3, 4, -1, -1, -1]);
console.log(getHeight(tree)); // 3

Complexity

• Time: O(n) — visit every node once during both build and height calculation.
• Space: O(n) — the tree itself, plus O(h) recursion stack where h is the height.

A shortcut you might miss

You don't actually need to build the tree. The height of a complete binary tree represented as an array is Math.floor(Math.log2(n)) + 1 where n is the number of non-null elements. But that only works for complete trees. The recursive approach handles any shape.