iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Trees

By · Reviewed & last updated · Part of Data Structures & Algorithms

A binary tree is the foundation of search structures, parsers, and many algorithms. Every node has up to two children. Three classic traversals: pre-, in-, post-order. Iterative versions use an explicit stack or queue.

Traversals + classic problems

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

// 1) Traversals — recursive
function inorder(root, out = []) {
    if (!root) return out;
    inorder(root.left,  out);
    out.push(root.val);
    inorder(root.right, out);
    return out;
}

function preorder(root, out = []) {
    if (!root) return out;
    out.push(root.val);
    preorder(root.left,  out);
    preorder(root.right, out);
    return out;
}

function postorder(root, out = []) {
    if (!root) return out;
    postorder(root.left,  out);
    postorder(root.right, out);
    out.push(root.val);
    return out;
}

// 2) Level order — BFS with a queue
function levelOrder(root) {
    if (!root) return [];
    const out = [], q = [root];
    while (q.length) {
        const level = [];
        for (let i = q.length; i > 0; i--) {
            const n = q.shift();
            level.push(n.val);
            if (n.left)  q.push(n.left);
            if (n.right) q.push(n.right);
        }
        out.push(level);
    }
    return out;
}

// 3) Max depth
const maxDepth = (root) => !root ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

// 4) Is this a valid BST?
function isBST(root, lo = -Infinity, hi = Infinity) {
    if (!root) return true;
    if (root.val <= lo || root.val >= hi) return false;
    return isBST(root.left, lo, root.val) && isBST(root.right, root.val, hi);
}

// 5) Lowest common ancestor (BST version — O(log n) amortised)
function lca(root, p, q) {
    while (root) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
}

Why it matters

Pre / in / post order differ only in WHEN you visit the node. Memorise the three template recursions and most tree problems collapse to “which template + do what at the visit?”.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

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

function inorder(root, out = []) {
    if (!root) return out;
    inorder(root.left, out);
    out.push(root.v);
    inorder(root.right, out);
    return out;
}
Try it Yourself »

Discussion

Loading…