jsschools

Binary Tree

A hierarchical data structure where each node has at most two children (left and right).

Spec ↗

Syntax

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

Parameters

NameTypeRequiredDescription
val any Yes The value stored at this node.
left TreeNode | null No Reference to the left child node.
right TreeNode | null No Reference to the right child node.

Returns

TreeNode — A new tree node that serves as the root of a subtree.

Examples

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

// In-order traversal (left → root → right)
function inorder(root, result = []) {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);
console.log(inorder(root));
Output 
[ 4, 2, 5, 1, 3 ]

// Level-order (BFS) traversal
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; 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;
}
console.log(levelOrder(root));
Output 
[ [ 1 ], [ 2, 3 ], [ 4, 5 ] ]

Notes

| Operation | Best | Avg | Worst | Space | |---------------|------|--------|-------|-------| | Search | O(1) | O(n) | O(n) | O(h) | | Insert | O(1) | O(n) | O(n) | O(h) | | Delete | O(1) | O(n) | O(n) | O(h) | | Traversal | O(n) | O(n) | O(n) | O(h) | h = height of the tree (O(log n) balanced, O(n) degenerate/skewed). Traversal orders: pre-order (root→L→R), in-order (L→root→R), post-order (L→R→root), level-order (BFS). A balanced binary tree with n nodes has height ⌊log₂ n⌋.

See also