A          ← root (no parent)
                /   \
               B     C        ← A is parent; B and C are children of A
              / \     \
             D   E     F      ← D, E, F are leaf nodes (no children)

  Node A: depth 0, level 1
  Node B: depth 1, level 2
  Node D: depth 2, level 3  ← leaf

  Height of tree = 2  (longest path root → leaf, counted in edges)
  Height of node B = 1 (longest path from B to a leaf below it)

class TreeNode {
  constructor(value) {
    this.value = value
    this.children = []   // N-ary: any number of children
  }
}

// Recursive height — height of a tree rooted at node
function height(node) {
  if (!node) return -1                     // empty tree: -1
  if (node.children.length === 0) return 0 // leaf: height 0
  return 1 + Math.max(...node.children.map(height))
}

// Recursive size — total number of nodes
function size(node) {
  if (!node) return 0
  return 1 + node.children.reduce((sum, child) => sum + size(child), 0)
}

       1
      / \
     2   3
    / \
   4   5

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

  left(3) < 8 < right(10)  ✓
  In-order traversal → 1 3 4 6 7 8 10 13 14  (sorted!)

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

function insert(root, val) {
  if (!root) return new BSTNode(val)
  if (val < root.val) root.left  = insert(root.left,  val)
  else                root.right = insert(root.right, val)
  return root
}

function search(root, val) {
  if (!root || root.val === val) return root
  return val < root.val ? search(root.left, val) : search(root.right, val)
}

// Build BST from array
function buildBST(values) {
  return values.reduce((root, v) => insert(root, v), null)
}

const bst = buildBST([8, 3, 10, 1, 6, 14, 4, 7, 13])
console.log(search(bst, 6)?.val)  // 6
console.log(search(bst, 99))      // null

  Unbalanced (BF = -2):      After left rotation:
        3                              5
         \                            / \
          5           →              3   7
           \
            7

  Balance factor must be in {-1, 0, 1} for every node.

          90
         /  \
        75   85
       /  \  / \
      55  60 70  80

  Array representation: [90, 75, 85, 55, 60, 70, 80]
  Parent of index i  → Math.floor((i - 1) / 2)
  Left child of i   → 2*i + 1
  Right child of i  → 2*i + 2

        root
       /    \
      c      b
      |      |
      a      a
     / \     |
    t   r    t*
   *   / \
      d*  e*

  * = end of word
  "car" shares "ca" with "cat" — prefix compression saves space.

class TrieNode {
  constructor() {
    this.children = {}   // char → TrieNode
    this.isEnd = false
  }
}

class Trie {
  constructor() { this.root = new TrieNode() }

  insert(word) {
    let node = this.root
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode()
      node = node.children[ch]
    }
    node.isEnd = true
  }

  search(word) {
    let node = this.root
    for (const ch of word) {
      if (!node.children[ch]) return false
      node = node.children[ch]
    }
    return node.isEnd
  }

  startsWith(prefix) {
    let node = this.root
    for (const ch of prefix) {
      if (!node.children[ch]) return false
      node = node.children[ch]
    }
    return true   // prefix exists (word may or may not be complete)
  }
}

const trie = new Trie()
;['cat', 'car', 'card', 'care', 'bat'].forEach(w => trie.insert(w))
console.log(trie.search('care'))      // true
console.log(trie.search('ca'))        // false (not a complete word)
console.log(trie.startsWith('ca'))    // true

  /
  ├── home/
  │   ├── user/
  │   │   ├── docs/
  │   │   └── pics/
  │   └── guest/
  └── etc/
      └── nginx/

function preOrder(node, result = []) {
  if (!node) return result
  result.push(node.val)          // Root
  preOrder(node.left,  result)   // Left
  preOrder(node.right, result)   // Right
  return result
}

function inOrder(node, result = []) {
  if (!node) return result
  inOrder(node.left,  result)    // Left
  result.push(node.val)          // Root
  inOrder(node.right, result)    // Right
  return result
}

function postOrder(node, result = []) {
  if (!node) return result
  postOrder(node.left,  result)  // Left
  postOrder(node.right, result)  // Right
  result.push(node.val)          // Root
  return result
}

function levelOrder(root) {
  if (!root) return []
  const result = [], queue = [root]
  while (queue.length) {
    const level = []
    const len = queue.length      // snapshot — important!
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left)  queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    result.push(level)
  }
  return result
}