Introduction to Binary Trees

tree = [1, 2, 3, 4, 5, 6, 7]       # a complete tree, level by level
i = 1                               # the node holding 2
left, right, parent = 2 * i + 1, 2 * i + 2, (i - 1) // 2
print(tree[left], tree[right], tree[parent])

i = 0                               # the root
for _ in range(19):                 # 19 steps down, always to the right child
    i = 2 * i + 2
print(i + 1)                        # slots the array needs to hold the last node

Reading the list with a queue of parents — Amber is the parent taking this entry, violet the child just placed; a crossed circle is a null.

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// A tree from LeetCode's level-order list; nullopt is a missing child.
TreeNode* build(const vector<optional<int>>& values) {
    if (values.empty() || !values[0]) return nullptr;
    TreeNode* root = new TreeNode(*values[0]);
    queue<TreeNode*> parents;                  // nodes still waiting for their children
    parents.push(root);
    size_t i = 1;
    while (!parents.empty() && i < values.size()) {
        TreeNode* parent = parents.front();
        parents.pop();
        if (values[i]) {                       // the next entry is the left child
            parent->left = new TreeNode(*values[i]);
            parents.push(parent->left);
        }
        i++;
        if (i < values.size() && values[i]) {  // the one after it, the right child
            parent->right = new TreeNode(*values[i]);
            parents.push(parent->right);
        }
        i++;
    }
    return root;
}

// The list back: level by level, null for each missing child, trailing nulls dropped.
string serialize(TreeNode* root) {
    vector<string> out;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (!node) {
            out.push_back("null");
            continue;
        }
        out.push_back(to_string(node->val));
        q.push(node->left);
        q.push(node->right);
    }
    while (!out.empty() && out.back() == "null") out.pop_back();
    string s = "[";
    for (size_t k = 0; k < out.size(); k++) s += (k ? ", " : "") + out[k];
    return s + "]";
}

from collections import deque


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


def build(values):
    """A tree from LeetCode's level-order list; None is a missing child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    parents = deque([root])                    # nodes still waiting for their children
    i = 1
    while parents and i < len(values):
        parent = parents.popleft()
        if values[i] is not None:              # the next entry is the left child
            parent.left = TreeNode(values[i])
            parents.append(parent.left)
        i += 1
        if i < len(values) and values[i] is not None:   # the one after it, the right child
            parent.right = TreeNode(values[i])
            parents.append(parent.right)
        i += 1
    return root


def serialize(root):
    """The list back: level by level, None for each missing child, trailing Nones dropped."""
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        queue.append(node.left)
        queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

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

// A tree from LeetCode's level-order list; null is a missing child.
static TreeNode build(Integer[] values) {
    if (values.length == 0 || values[0] == null) return null;
    TreeNode root = new TreeNode(values[0]);
    Deque<TreeNode> parents = new ArrayDeque<>();   // nodes still waiting for their children
    parents.add(root);
    int i = 1;
    while (!parents.isEmpty() && i < values.length) {
        TreeNode parent = parents.poll();
        if (values[i] != null) {                      // the next entry is the left child
            parent.left = new TreeNode(values[i]);
            parents.add(parent.left);
        }
        i++;
        if (i < values.length && values[i] != null) { // the one after it, the right child
            parent.right = new TreeNode(values[i]);
            parents.add(parent.right);
        }
        i++;
    }
    return root;
}

// The list back: level by level, null for each missing child, trailing nulls dropped.
static String serialize(TreeNode root) {
    List<String> out = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();       // it holds nulls, which an ArrayDeque refuses
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            out.add("null");
            continue;
        }
        out.add(String.valueOf(node.val));
        queue.add(node.left);
        queue.add(node.right);
    }
    while (!out.isEmpty() && out.get(out.size() - 1).equals("null")) out.remove(out.size() - 1);
    return "[" + String.join(", ", out) + "]";
}

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// A tree from LeetCode's level-order list; null is a missing child.
function build(values) {
    if (values.length === 0 || values[0] === null) return null;
    const root = new TreeNode(values[0]);
    const parents = [root];                // nodes still waiting for their children
    let head = 0;                          // the front of that queue, with no shift()
    let i = 1;
    while (head < parents.length && i < values.length) {
        const parent = parents[head++];
        if (values[i] !== null) {                       // the next entry is the left child
            parent.left = new TreeNode(values[i]);
            parents.push(parent.left);
        }
        i++;
        if (i < values.length && values[i] !== null) {  // the one after it, the right child
            parent.right = new TreeNode(values[i]);
            parents.push(parent.right);
        }
        i++;
    }
    return root;
}

// The list back: level by level, null for each missing child, trailing nulls dropped.
function serialize(root) {
    const out = [];
    const queue = [root];
    for (let head = 0; head < queue.length; head++) {
        const node = queue[head];
        if (node === null) {
            out.push(null);
            continue;
        }
        out.push(node.val);
        queue.push(node.left, node.right);
    }
    while (out.length && out[out.length - 1] === null) out.pop();
    return "[" + out.map((v) => (v === null ? "null" : v)).join(", ") + "]";
}

// LeetCode's maximum depth: the nodes on the longest path from the root down.
int maxDepth(TreeNode* node) {
    if (node == nullptr) return 0;           // an empty tree has no levels
    return 1 + max(maxDepth(node->left), maxDepth(node->right));
}

def max_depth(node):
    """LeetCode's maximum depth: the nodes on the longest path from the root down."""
    if node is None:                         # an empty tree has no levels
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

// LeetCode's maximum depth: the nodes on the longest path from the root down.
static int maxDepth(TreeNode node) {
    if (node == null) return 0;              // an empty tree has no levels
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

// LeetCode's maximum depth: the nodes on the longest path from the root down.
function maxDepth(node) {
    if (node === null) return 0;             // an empty tree has no levels
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

Maximum depth, answered from the leaves up — Indigo is the call being worked on, amber the calls waiting on it, violet the nodes that have answered, with the answer on their badge.

// The mirror image: every node's two children swap places.
TreeNode* invert(TreeNode* node) {
    if (node == nullptr) return nullptr;
    TreeNode* left = invert(node->left);     // both answers first,
    TreeNode* right = invert(node->right);
    node->left = right;                       // then swap them in
    node->right = left;
    return node;
}

def invert(node):
    """The mirror image: every node's two children swap places."""
    if node is None:
        return None
    left = invert(node.left)                 # both answers first,
    right = invert(node.right)
    node.left = right                        # then swap them in
    node.right = left
    return node

// The mirror image: every node's two children swap places.
static TreeNode invert(TreeNode node) {
    if (node == null) return null;
    TreeNode left = invert(node.left);       // both answers first,
    TreeNode right = invert(node.right);
    node.left = right;                        // then swap them in
    node.right = left;
    return node;
}

// The mirror image: every node's two children swap places.
function invert(node) {
    if (node === null) return null;
    const left = invert(node.left);          // both answers first,
    const right = invert(node.right);
    node.left = right;                        // then swap them in
    node.right = left;
    return node;
}

Invert, from the bottom up — Indigo is the node swapping its subtrees; orange marks the two children that just traded places, each bringing its subtree along.

// The same maximum depth, with the waiting work on a stack of (node, depth) pairs.
int maxDepth(TreeNode* root) {
    int best = 0;
    vector<pair<TreeNode*, int>> stack;
    if (root) stack.push_back({root, 1});
    while (!stack.empty()) {
        auto [node, depth] = stack.back();
        stack.pop_back();
        best = max(best, depth);
        if (node->left) stack.push_back({node->left, depth + 1});
        if (node->right) stack.push_back({node->right, depth + 1});
    }
    return best;
}

def max_depth(root):
    """The same maximum depth, with the waiting work on a stack of (node, depth) pairs."""
    best = 0
    stack = [(root, 1)] if root else []
    while stack:
        node, depth = stack.pop()
        best = max(best, depth)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return best

// The same maximum depth, with the waiting work on a stack of (node, depth) pairs.
static int maxDepth(TreeNode root) {
    int best = 0;
    Deque<TreeNode> nodes = new ArrayDeque<>();
    Deque<Integer> depths = new ArrayDeque<>();
    if (root != null) {
        nodes.push(root);
        depths.push(1);
    }
    while (!nodes.isEmpty()) {
        TreeNode node = nodes.pop();
        int depth = depths.pop();
        best = Math.max(best, depth);
        if (node.left != null) {
            nodes.push(node.left);
            depths.push(depth + 1);
        }
        if (node.right != null) {
            nodes.push(node.right);
            depths.push(depth + 1);
        }
    }
    return best;
}

// The same maximum depth, with the waiting work on a stack of (node, depth) pairs.
function maxDepth(root) {
    let best = 0;
    const stack = root ? [[root, 1]] : [];
    while (stack.length) {
        const [node, depth] = stack.pop();
        best = Math.max(best, depth);
        if (node.left) stack.push([node.left, depth + 1]);
        if (node.right) stack.push([node.right, depth + 1]);
    }
    return best;
}

def build_by_index(values, i=0):
    """Wrong: reads LeetCode's list as if the children of i were at 2i + 1 and 2i + 2."""
    if i >= len(values) or values[i] is None:
        return None
    node = TreeNode(values[i])
    node.left = build_by_index(values, 2 * i + 1)
    node.right = build_by_index(values, 2 * i + 2)
    return node

def max_depth(node):
    if node is None:
        return -1                    # wrong: counts edges, the problem counts nodes
    return 1 + max(max_depth(node.left), max_depth(node.right))

def invert(node):
    if node is None:
        return None
    node.left = invert(node.right)   # wrong: overwrites node.left ...
    node.right = invert(node.left)   # ... then inverts what it just wrote
    return node

def max_depth(node):                 # wrong: no case for the empty tree
    return 1 + max(max_depth(node.left), max_depth(node.right))