🌳 JavaScript Tree Basics

Node Class

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

---

Building a Binary Tree Manually

const root       = new TreeNode(1);
root.left        = new TreeNode(2);
root.right       = new TreeNode(3);
root.left.left   = new TreeNode(4);
root.left.right  = new TreeNode(5);

//       1
//      / \
//     2   3
//    / \
//   4   5

---

Key Terminology

---

Binary Search Tree (BST)

A BST satisfies: left < root < right at every node.

class BST {
    constructor() { this.root = null; }

    insert(val) {
        this.root = this._insert(this.root, val);
    }
    _insert(node, val) {
        if (!node) return new TreeNode(val);
        if (val < node.val)      node.left  = this._insert(node.left,  val);
        else if (val > node.val) node.right = this._insert(node.right, val);
        return node;
    }

    search(val) { return this._search(this.root, val); }
    _search(node, val) {
        if (!node)           return false;
        if (val === node.val) return true;
        return val < node.val
            ? this._search(node.left,  val)
            : this._search(node.right, val);
    }
}

const bst = new BST();
[5, 3, 7, 1, 4].forEach(v => bst.insert(v));
console.log(bst.search(4)); // true
console.log(bst.search(6)); // false

Time: O(log n) average, O(n) worst | Space: O(h)

---

Tree Height

function height(node) {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

Time: O(n) | Space: O(h)

---

Count Nodes

function countNodes(node) {
    if (!node) return 0;
    return 1 + countNodes(node.left) + countNodes(node.right);
}

---

Check if Balanced

function isBalanced(root) {
    return checkHeight(root) !== -1;
}
function checkHeight(node) {
    if (!node) return 0;
    const l = checkHeight(node.left);
    if (l === -1) return -1;
    const r = checkHeight(node.right);
    if (r === -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

Time: O(n) | Space: O(h)

---

Complexity Summary