Tree functions
Each snippet below is something you will reach for while solving tree problems. Skim the short description, then copy the TypeScript for common shapes.
Prefer Overview for how trees work, and Problems for practice once problems are linked.
Node shape
A binary tree node holds a value and optional left and right children.
TreeNode
The usual interview shape — value plus left and right links.
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
function treeNode(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
return { val, left, right };
}
// ——— leaf ———
const leaf = treeNode(1);
// ——— small tree ———
const root = treeNode(2, treeNode(1), treeNode(3));N-ary node
When a node can have many children, store them in an array.
type NaryNode = {
val: number;
children: NaryNode[];
};
function naryNode(val: number, children: NaryNode[] = []): NaryNode {
return { val, children };
}
const root = naryNode(1, [naryNode(2), naryNode(3), naryNode(4)]);Building a tree
Turn a level-order list (or nested pairs) into linked nodes.
fromLevelOrder()
Builds a binary tree from a LeetCode-style array with null gaps.
function fromLevelOrder(values: (number | null)[]): TreeNode | null {
if (values.length === 0 || values[0] == null) return null;
const root: TreeNode = { val: values[0], left: null, right: null };
const queue: TreeNode[] = [root];
let i = 1;
while (queue.length > 0 && i < values.length) {
const node = queue.shift()!;
const leftVal = values[i++];
if (leftVal != null) {
node.left = { val: leftVal, left: null, right: null };
queue.push(node.left);
}
if (i >= values.length) break;
const rightVal = values[i++];
if (rightVal != null) {
node.right = { val: rightVal, left: null, right: null };
queue.push(node.right);
}
}
return root;
}
// [8, 3, 10, 1, 6, null, 14]
const root = fromLevelOrder([8, 3, 10, 1, 6, null, 14]);Manual nesting
Fine for tiny examples in tests or whiteboard sketches.
const root: TreeNode = {
val: 8,
left: {
val: 3,
left: { val: 1, left: null, right: null },
right: { val: 6, left: null, right: null },
},
right: {
val: 10,
left: null,
right: { val: 14, left: null, right: null },
},
};Depth-first walks
Go deep on one path, then backtrack. Order depends on when you visit the node.
preorder()
Visit node, then left, then right — root first.
function preorder(root: TreeNode | null, out: number[] = []): number[] {
if (!root) return out;
out.push(root.val);
preorder(root.left, out);
preorder(root.right, out);
return out;
}
// iterative with an explicit stack
function preorderIter(root: TreeNode | null): number[] {
if (!root) return [];
const out: number[] = [];
const stack: TreeNode[] = [root];
while (stack.length > 0) {
const node = stack.pop()!;
out.push(node.val);
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return out;
}inorder()
Left, node, right — for a BST this visits values in sorted order.
function inorder(root: TreeNode | null, out: number[] = []): number[] {
if (!root) return out;
inorder(root.left, out);
out.push(root.val);
inorder(root.right, out);
return out;
}postorder()
Left, right, then node — useful when children must finish first (delete, compute).
function postorder(root: TreeNode | null, out: number[] = []): number[] {
if (!root) return out;
postorder(root.left, out);
postorder(root.right, out);
out.push(root.val);
return out;
}Level-order (BFS)
Visit every node on a level before going deeper — queue does the bookkeeping.
levelOrder()
Returns values grouped by level, top to bottom, left to right.
function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const result: number[][] = [];
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const size = queue.length;
const level: number[] = [];
for (let i = 0; i < size; 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;
}flatLevelOrder()
Same walk, but one flat list — handy for serialization sketches.
function flatLevelOrder(root: TreeNode | null): number[] {
if (!root) return [];
const out: number[] = [];
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const node = queue.shift()!;
out.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return out;
}Binary search tree
Left subtree values are smaller; right subtree values are larger. Search and insert follow comparisons.
bstSearch()
Walk left or right by comparing with the current node.
function bstSearch(root: TreeNode | null, target: number): TreeNode | null {
let cur = root;
while (cur) {
if (target === cur.val) return cur;
cur = target < cur.val ? cur.left : cur.right;
}
return null;
}bstInsert()
Walk to a null child slot, then hang the new node there.
function bstInsert(root: TreeNode | null, val: number): TreeNode {
const fresh: TreeNode = { val, left: null, right: null };
if (!root) return fresh;
let cur = root;
while (true) {
if (val < cur.val) {
if (!cur.left) {
cur.left = fresh;
return root;
}
cur = cur.left;
} else {
if (!cur.right) {
cur.right = fresh;
return root;
}
cur = cur.right;
}
}
}Size & height
Count nodes, or measure the longest root-to-leaf path.
size()
How many nodes are in the tree?
function size(root: TreeNode | null): number {
if (!root) return 0;
return 1 + size(root.left) + size(root.right);
}height()
Edges on the longest path down from this node (empty tree → -1 or 0 by convention).
// height of empty = -1 so a single node has height 0
function height(root: TreeNode | null): number {
if (!root) return -1;
return 1 + Math.max(height(root.left), height(root.right));
}
// depth of a node from the root (root depth = 0)
function depth(root: TreeNode | null, target: number, d = 0): number {
if (!root) return -1;
if (root.val === target) return d;
const left = depth(root.left, target, d + 1);
if (left !== -1) return left;
return depth(root.right, target, d + 1);
}Serialize sketch
Flatten a tree to a string (or array), then rebuild — useful for cloning and wire formats.
serialize()
Level-order with null markers so shape is preserved.
function serialize(root: TreeNode | null): string {
if (!root) return '';
const parts: string[] = [];
const queue: (TreeNode | null)[] = [root];
while (queue.length > 0) {
const node = queue.shift()!;
if (!node) {
parts.push('#');
continue;
}
parts.push(String(node.val));
queue.push(node.left);
queue.push(node.right);
}
// trim trailing nulls
while (parts.length > 0 && parts[parts.length - 1] === '#') parts.pop();
return parts.join(',');
}deserialize()
Rebuild from the serialize() string.
function deserialize(data: string): TreeNode | null {
if (data.length === 0) return null;
const parts = data.split(',');
const root: TreeNode = { val: Number(parts[0]), left: null, right: null };
const queue: TreeNode[] = [root];
let i = 1;
while (queue.length > 0 && i < parts.length) {
const node = queue.shift()!;
if (parts[i] !== '#') {
node.left = { val: Number(parts[i]), left: null, right: null };
queue.push(node.left);
}
i += 1;
if (i >= parts.length) break;
if (parts[i] !== '#') {
node.right = { val: Number(parts[i]), left: null, right: null };
queue.push(node.right);
}
i += 1;
}
return root;
}