A tree is a hierarchical data structure consisting of nodes connected by edges. It has a root node, and each node can have zero or more children.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
Trees are used in file systems, DOM, compilers (AST), databases (B-trees), and more.
A binary tree is a tree where each node has at most two children: left and right.
// 1
// / \
// 2 3
// / \
// 4 5
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);
A perfect binary tree of height h has 2^(h+1) - 1 nodes.
Three DFS traversal orders for binary trees:
function inorder(node, result = []) {
if (!node) return result;
inorder(node.left, result);
result.push(node.val);
inorder(node.right, result);
return result;
}
function preorder(node, result = []) {
if (!node) return result;
result.push(node.val);
preorder(node.left, result);
preorder(node.right, result);
return result;
}
function postorder(node, result = []) {
if (!node) return result;
postorder(node.left, result);
postorder(node.right, result);
result.push(node.val);
return result;
}
All three are O(n) time and O(h) space (recursion stack).
Level order traversal visits nodes level by level using a queue.
function levelOrder(root) {
if (!root) return [];
const result = [];
const 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;
}
// 1
// / \
// 2 3
// / \
// 4 5
// => [[1], [2, 3], [4, 5]]
Time: O(n) | Space: O(w) where w is the maximum width of the tree.
The height is the number of edges on the longest path from root to a leaf. Use recursion: the height is 1 + max(left height, right height).
function treeHeight(node) {
if (!node) return -1; // -1 for edge count, 0 for node count
return 1 + Math.max(treeHeight(node.left), treeHeight(node.right));
}
// Alternative: return 0 if null (counts nodes on longest path)
function maxDepth(node) {
if (!node) return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
// 1
// / \
// 2 3
// /
// 4
// treeHeight => 2 (edges), maxDepth => 3 (nodes)
Time: O(n) | Space: O(h) recursion stack.
Recursively count: 1 (current node) + count of left subtree + count of right subtree.
function countNodes(node) {
if (!node) return 0;
return 1 + countNodes(node.left) + countNodes(node.right);
}
// Count leaf nodes only:
function countLeaves(node) {
if (!node) return 0;
if (!node.left && !node.right) return 1;
return countLeaves(node.left) + countLeaves(node.right);
}
// 1
// / \
// 2 3
// / \
// 4 5
// countNodes => 5, countLeaves => 3 (nodes 3, 4, 5)
Time: O(n) | Space: O(h)
A tree is balanced if for every node, the height difference between left and right subtrees is at most 1.
function isBalanced(node) {
function checkHeight(node) {
if (!node) return 0;
const left = checkHeight(node.left);
if (left === -1) return -1;
const right = checkHeight(node.right);
if (right === -1) return -1;
if (Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}
return checkHeight(node) !== -1;
}
// Balanced: Unbalanced:
// 1 1
// / \ \
// 2 3 2
// \
// 3
Time: O(n) — each node visited once | Space: O(h)
Swap the left and right children of every node recursively.
function invertTree(node) {
if (!node) return null;
const temp = node.left;
node.left = node.right;
node.right = temp;
invertTree(node.left);
invertTree(node.right);
return node;
}
// Before: After:
// 1 1
// / \ / \
// 2 3 3 2
// / \ / \
// 4 5 5 4
Time: O(n) | Space: O(h). This is a classic interview question famously associated with Homebrew creator Max Howell.
The diameter is the longest path between any two nodes (number of edges). It may or may not pass through the root.
function diameterOfBinaryTree(root) {
let diameter = 0;
function height(node) {
if (!node) return 0;
const left = height(node.left);
const right = height(node.right);
diameter = Math.max(diameter, left + right);
return 1 + Math.max(left, right);
}
height(root);
return diameter;
}
// 1
// / \
// 2 3
// / \
// 4 5
// Diameter = 3 (path: 4->2->1->3 or 5->2->1->3)
Time: O(n) | Space: O(h)
The LCA of nodes p and q is the deepest node that is an ancestor of both. If a node finds p on one side and q on the other, it is the LCA.
function lowestCommonAncestor(root, p, q) {
if (!root || root === p || root === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root; // p and q on different sides
return left || right;
}
// 3
// / \
// 5 1
// / \
// 6 2
// LCA(5, 1) = 3
// LCA(6, 2) = 5
Time: O(n) | Space: O(h). For BSTs, you can optimize by comparing values to avoid visiting all nodes.
The diameter is the longest path between any two nodes. At each node, the diameter passing through it = left_height + right_height. Track the global max.
function diameterOfBinaryTree(root) {
let maxDia = 0;
function height(node) {
if (!node) return 0;
const left = height(node.left);
const right = height(node.right);
maxDia = Math.max(maxDia, left + right); // path through this node
return 1 + Math.max(left, right);
}
height(root);
return maxDia;
}
// Tree: 1
// / // 2 3
// / // 4 5
// Output: 3 (path: 4->2->1->3 or 5->2->1->3, length = 3 edges)
Time: O(n) | Space: O(h)
Recursively compare: both null = same, one null = different, both present = compare values and recursively compare all children.
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p.val === q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
// Both trees same structure and values => true
// Structural difference => false
// Same structure but different values => false
Time: O(n) | Space: O(h)
At each node of the main tree, check if the subtree rooted there is the same as the given subtree using isSameTree.
function isSubtree(root, subRoot) {
if (!root) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
// Main tree contains subRoot structure => true
// subRoot not found anywhere => false
Time: O(m × n) worst case | Space: O(h)
At each node, the max path through it = left_gain + right_gain + node.val. Only include a subtree's contribution if it's positive. Track global max.
function maxPathSum(root) {
let maxSum = -Infinity;
function gain(node) {
if (!node) return 0;
const leftGain = Math.max(gain(node.left), 0);
const rightGain = Math.max(gain(node.right), 0);
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
return node.val + Math.max(leftGain, rightGain); // only one branch!
}
gain(root);
return maxSum;
}
// Tree: -10 with children 9 and 20(left:15, right:7)
// Output: 42 (path: 15->20->7)
Time: O(n) | Space: O(h)
Serialize using pre-order DFS, encode null nodes as #. Deserialize by rebuilding pre-order, consuming tokens from a queue.
function serialize(root) {
const result = [];
function dfs(node) {
if (!node) { result.push('#'); return; }
result.push(node.val);
dfs(node.left);
dfs(node.right);
}
dfs(root);
return result.join(',');
}
function deserialize(data) {
const tokens = data.split(',');
let i = 0;
function build() {
if (tokens[i] === '#') { i++; return null; }
const node = { val: Number(tokens[i++]) };
node.left = build();
node.right = build();
return node;
}
return build();
}
// Tree 1,2,3 serializes to "1,2,#,#,3,#,#"
// Deserializing "1,2,#,#,3,#,#" => restores original tree
Time: O(n) | Space: O(n)
A node is good if no value in the path from root to it is greater than it. Do a DFS tracking the max value seen so far on the path.
function goodNodes(root) {
function dfs(node, maxSoFar) {
if (!node) return 0;
const isGood = node.val >= maxSoFar ? 1 : 0;
const newMax = Math.max(maxSoFar, node.val);
return isGood + dfs(node.left, newMax) + dfs(node.right, newMax);
}
return dfs(root, -Infinity);
}
// Tree: 3, left=1(left=3), right=4(left=1, right=5)
// Good nodes: 3, 3, 4, 5 => Output: 4
Time: O(n) | Space: O(h)
The first element in pre-order is the root. Find it in in-order to split left/right subtrees. Recursively build each subtree.
function buildTree(preorder, inorder) {
const inMap = new Map(inorder.map((v, i) => [v, i]));
function build(preL, preR, inL, inR) {
if (preL > preR) return null;
const rootVal = preorder[preL];
const inIdx = inMap.get(rootVal);
const leftSize = inIdx - inL;
const node = { val: rootVal };
node.left = build(preL+1, preL+leftSize, inL, inIdx-1);
node.right = build(preL+leftSize+1, preR, inIdx+1, inR);
return node;
}
return build(0, preorder.length-1, 0, inorder.length-1);
}
// preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]
// => Builds: 3(left=9, right=20(left=15, right=7))
Time: O(n) | Space: O(n)
Use DFS. Track path and remaining sum. At each leaf, if remaining equals node.val, save the path.
function pathSum(root, target) {
const result = [];
function dfs(node, remaining, path) {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right && remaining === node.val) {
result.push([...path]);
}
dfs(node.left, remaining - node.val, path);
dfs(node.right, remaining - node.val, path);
path.pop(); // backtrack
}
dfs(root, target, []);
return result;
}
// Tree: 5(4(11(7,2)), 8(13,4(5,1))), target=22
// Output: [[5,4,11,2],[5,8,4,5]]
Time: O(n²) worst case (copying paths) | Space: O(n)
Use the Morris traversal trick: for each node that has a left child, find the rightmost node of the left subtree, attach the right child there, then move left to right.
function flatten(root) {
let curr = root;
while (curr) {
if (curr.left) {
// Find rightmost of left subtree
let rightmost = curr.left;
while (rightmost.right) rightmost = rightmost.right;
// Re-wire
rightmost.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}
// Tree: 1(2(3,4), 5(null,6))
// After flatten: 1->2->3->4->5->6 (all right pointers)
Time: O(n) | Space: O(1) no recursion stack
Use BFS level by level and take the last node of each level, or use DFS tracking depth and only recording the first visit at each depth from the right.
function rightSideView(root) {
if (!root) return [];
const result = [];
let queue = [root];
while (queue.length) {
result.push(queue[queue.length-1].val); // rightmost at level
const next = [];
for (const node of queue) {
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
}
return result;
}
// Tree: 1
// / // 2 3
// // 5 4
// Output: [1, 3, 4]
Time: O(n) | Space: O(w) max level width
Recursively compare the left and right subtrees as mirrors: outer values match and inner subtrees are mirror reflections of each other.
function isSymmetric(root) {
function isMirror(left, right) {
if (!left && !right) return true;
if (!left || !right) return false;
return left.val === right.val
&& isMirror(left.left, right.right)
&& isMirror(left.right, right.left);
}
return isMirror(root?.left, root?.right);
}
// Symmetric tree: 1
// / // 2 2
// / / // 3 4 4 3 => Output: true
// Asymmetric: 1(2(null,3), 2(null,3)) => false
Time: O(n) | Space: O(h)
Use DFS backtracking. Maintain a path array; push on entry, pop on exit. When a leaf is reached, record the current path.
function binaryTreePaths(root) {
const result = [];
function dfs(node, path) {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right) {
result.push(path.join('->'));
}
dfs(node.left, path);
dfs(node.right, path);
path.pop(); // backtrack
}
dfs(root, []);
return result;
}
// Tree: 1
// / // 2 3
// // 5
// Output: ["1->2->5", "1->3"]
Time: O(n) | Space: O(n)
Use BFS and stop at the desired depth, OR use DFS passing the current depth; collect node values when depth matches.
function nodesAtDepth(root, targetDepth) {
const result = [];
function dfs(node, depth) {
if (!node) return;
if (depth === targetDepth) { result.push(node.val); return; }
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
dfs(root, 0);
return result;
}
// Tree: 1 depth 0
// / // 2 3 depth 1
// / // 4 5 depth 2
// nodesAtDepth(root, 2) => [4, 5]
Time: O(n) | Space: O(h)
Recursively sum: nodeSum = node.val + sum(left) + sum(right). Base case: null node returns 0.
function treeSum(root) {
if (!root) return 0;
return root.val + treeSum(root.left) + treeSum(root.right);
}
// Iterative BFS version:
function treeSumBFS(root) {
if (!root) return 0;
let sum = 0;
const queue = [root];
while (queue.length) {
const node = queue.shift();
sum += node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return sum;
}
// Tree: 1(left=2, right=3(left=4, right=5))
// Output: 15
Time: O(n) | Space: O(h) for DFS, O(w) for BFS