Tracks

Full-Stack Interview Prep

AI Engineering Roadmap →

Binary Trees

19 problems · 30 approaches

← Checklist · All topics →

Level order traversalEasy1 approach

Problem

Return the tree's node values level by level, from top to bottom and left to right within each level, as a list of levels.

Example 1

Input:  root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]

1. BFS with a queue

Time O(n)Space O(width)

Process the tree one level at a time; the queue length at the start of each round is the level size.

function levelOrder(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const level = [];
    for (let k = q.length; k > 0; k--) {
      const node = q.shift();
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    res.push(level);
  }
  return res;
}
Find the Lowest Common Ancestor in a Binary TreeMedium2 approaches

Problem

Given a binary tree (not a BST) and two nodes p and q, return their lowest common ancestor: the deepest node that has both p and q as descendants. A node counts as a descendant of itself.

Example 1

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Example 2

Input:  same tree, p = 5, q = 4
Output: 5

Also asked as: lca · lowest common ancestor in a BST · Find LCA of 2 nodes in a BST · Find LCA of 2 nodes in a BST · Find LCA in a Binary tree

1. Post-order recursion (general binary tree)

Time O(n)Space O(h)

Return the node where p is found on one side and q on the other; that split point is the LCA.

function lca(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lca(root.left, p, q);
  const right = lca(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

2. BST short-cut

Time O(h)Space O(1)

In a BST, walk down: go left if both targets are smaller, right if both larger, else you are at the LCA.

function lcaBST(root, p, q) {
  let n = root;
  while (n) {
    if (p.val < n.val && q.val < n.val) n = n.left;
    else if (p.val > n.val && q.val > n.val) n = n.right;
    else return n;
  }
}
Diameter of a Binary TreeEasy1 approach

Problem

Return the diameter of the tree: the number of edges on the longest path between any two nodes. The path does not have to pass through the root.

Example 1

Input:  [1, 2, 3, 4, 5]
Output: 3

The path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3).

Also asked as: Diameter of a tree

1. DFS returning height, update diameter as a side effect

Time O(n)Space O(h)

At each node, the longest path through it is leftHeight + rightHeight; track the max.

function diameterOfBinaryTree(root) {
  let best = 0;
  const height = (n) => {
    if (!n) return 0;
    const l = height(n.left), r = height(n.right);
    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
  };
  height(root);
  return best;
}
All tree traversals — inorder, preorder, postorder (recursive & iterative), level order, zig-zagEasy3 approaches

Problem

Produce the standard traversals of a binary tree:

Inorder (left, node, right), preorder (node, left, right) and postorder (left, right, node) — both recursively and iteratively with an explicit stack.

Level order (top to bottom), reverse level order, and zig-zag (alternate left→right and right→left on each level).

Example 1

Input:  root = [1, 2, 3, 4, 5]  (2 has children 4, 5)
Output: in: 4 2 5 1 3 · pre: 1 2 4 5 3 · post: 4 5 2 3 1 · zig-zag: [[1], [3, 2], [4, 5]]

Also asked as: Inorder Traversal of a tree both using recursion and Iteration · Preorder Traversal of a tree both using recursion and Iteration · Postorder Traversal of a tree both using recursion and Iteration · Reverse Level Order traversal · Zig-Zag traversal of a binary tree

1. Recursive DFS (the three orders)

Time O(n)Space O(h)

Visit the node before / between / after its children for pre / in / post order.

const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
const preorder = (n, out = []) => { if (n) { out.push(n.val); preorder(n.left, out); preorder(n.right, out); } return out; };
const postorder = (n, out = []) => { if (n) { postorder(n.left, out); postorder(n.right, out); out.push(n.val); } return out; };

2. Iterative with an explicit stack

Time O(n)Space O(h)

Preorder: push right then left. Inorder: push all lefts, pop-visit-go-right. Postorder: do a reversed "root-right-left" preorder.

function inorderIter(root) {
  const out = [], st = [];
  let cur = root;
  while (cur || st.length) {
    while (cur) { st.push(cur); cur = cur.left; }
    cur = st.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}
function postorderIter(root) {
  const out = [], st = root ? [root] : [];
  while (st.length) {
    const n = st.pop();
    out.push(n.val);
    if (n.left) st.push(n.left);
    if (n.right) st.push(n.right);
  }
  return out.reverse();
}

3. Level order, reverse level order, zig-zag (BFS)

Time O(n)Space O(width)

BFS one level at a time. Reverse level order: reverse the collected levels (or unshift). Zig-zag: reverse alternate levels.

function zigzag(root) {
  if (!root) return [];
  const res = [], q = [root];
  let leftToRight = true;
  while (q.length) {
    const level = [];
    for (let k = q.length; k > 0; k--) {
      const n = q.shift();
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(leftToRight ? level : level.reverse());
    leftToRight = !leftToRight;
  }
  return res;
}
// reverse level order = build levels normally, then res.reverse()
Height, balance check, and mirror of a treeEasy2 approaches

Problem

Three basic recursions. Height (maximum depth): the number of nodes on the longest root-to-leaf path. Balanced: at every node, the heights of the two subtrees differ by at most 1. Mirror (invert): swap every node's left and right children.

Example 1

Input:  [3, 9, 20, null, null, 15, 7]
Output: height 3, balanced true

Example 2

Input:  mirror of [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]

Also asked as: Height of a tree · Check if a tree is balanced or not · Mirror of a tree · Check if 2 trees are mirror or not · Tree Isomorphism Problem

1. One DFS returning height (−1 signals imbalance)

Time O(n)Space O(h)

Height = 1 + max(childHeights). Balanced iff every node’s subtree heights differ by ≤ 1 — propagate −1 upward on the first violation.

function height(n) { return n ? 1 + Math.max(height(n.left), height(n.right)) : 0; }


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

2. Mirror (invert) and "are two trees mirrors?"

Time O(n)Space O(h)

Invert: swap children recursively. Two trees are mirrors iff a.left ≡ mirror of b.right and a.right ≡ mirror of b.left.

function mirror(n) {
  if (!n) return null;
  [n.left, n.right] = [mirror(n.right), mirror(n.left)];
  return n;
}
function areMirror(a, b) {
  if (!a && !b) return true;
  if (!a || !b || a.val !== b.val) return false;
  return areMirror(a.left, b.right) && areMirror(a.right, b.left);
}
// Isomorphic: like areMirror but allow EITHER (same children) OR (swapped children).
Tree views — left, right, top, bottom, diagonal, boundaryMedium3 approaches

Problem

Return what is visible from different sides of the tree:

Left / right view — the first / last node on each level. Top / bottom view — the first / last node seen in each vertical column (horizontal distance: root 0, left −1, right +1). Diagonal traversal — group nodes along lines of slope −1. Boundary traversal — the left boundary, then the leaves, then the right boundary in reverse, going anticlockwise.

Example 1

Input:  root = [1, 2, 3, 4, 5, 6, 7]
Output: left [1,2,4] · right [1,3,7] · top [4,2,1,3,7] · bottom [4,2,6,3,7] (5 and 6 share a column; the later one wins)

Also asked as: Left View of a tree · Right View of Tree · Top View of a tree · Bottom View of a tree · Diagnol Traversal of a Binary tree · Boundary traversal of a Binary tree

1. Left / Right view — first node seen per BFS level

Time O(n)Space O(width)

Level-order BFS; the first node dequeued at each level is the left view, the last is the right view.

function rightView(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const n = q.length;
    for (let i = 0; i < n; i++) {
      const node = q.shift();
      if (i === n - 1) res.push(node.val);        // last of the level = right view
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
  }
  return res;
}

2. Top / Bottom view — by horizontal distance

Time O(n log n)Space O(n)

BFS carrying a horizontal distance (hd): left child hd−1, right child hd+1. Top view keeps the first node per hd; bottom view keeps the last. Sort by hd.

function bottomView(root) {
  if (!root) return [];
  const map = new Map();
  const q = [[root, 0]];
  while (q.length) {
    const [node, hd] = q.shift();
    map.set(hd, node.val);                        // last write wins ⇒ bottom
    if (node.left) q.push([node.left, hd - 1]);
    if (node.right) q.push([node.right, hd + 1]);
  }
  return [...map.entries()].sort((a, b) => a[0] - b[0]).map(([, v]) => v);
}
// Top view: same, but only set map if the hd is not already present.

3. Diagonal & boundary traversals

Time O(n)Space O(n)

Diagonal: right edges stay on the same diagonal, left edges start the next — use a queue of "diagonal starts". Boundary: left boundary (top-down, no leaves) + all leaves (left-to-right) + right boundary (bottom-up, no leaves).

function diagonal(root) {
  const res = [];
  let queue = root ? [root] : [];
  while (queue.length) {
    const next = [];
    for (let node of queue) {
      while (node) {
        res.push(node.val);
        if (node.left) next.push(node.left);
        node = node.right;
      }
    }
    queue = next;
  }
  return res;
}
Construct a binary tree from inorder + preorderMedium1 approach

Problem

Given the preorder and inorder traversals of a binary tree with unique values, rebuild the tree and return its root.

Example 1

Input:  preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]

Also asked as: Construct Binary tree from Inorder and preorder traversal

1. Recursion with an index map for inorder

Time O(n)Space O(n)

The next preorder value is the current root; its position in inorder splits the array into left and right subtrees.

function buildTree(preorder, inorder) {
  const pos = new Map(inorder.map((v, i) => [v, i]));
  let p = 0;
  const build = (lo, hi) => {
    if (lo > hi) return null;
    const rootVal = preorder[p++];
    const node = { val: rootVal, left: null, right: null };
    const mid = pos.get(rootVal);
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  };
  return build(0, inorder.length - 1);
}
Construct a binary tree from its bracket string representationMedium1 approach

Problem

The string encodes a tree as a value followed by zero, one or two parenthesised subtrees: the first pair is the left child, the second is the right. Build the tree.

Example 1

Input:  "4(2(3)(1))(6(5))"
Output: 4 with left 2 (children 3, 1) and right 6 (left child 5)

Also asked as: Construct Binary Tree from String with Bracket Representation

1. Recursive descent parser

Time O(n)Space O(h)

A number is a node; an opening "(" begins its left child, a second "(" its right child; ")" closes.

function str2tree(s) {
  let i = 0;
  const parse = () => {
    let sign = 1;
    if (s[i] === '-') { sign = -1; i++; }
    let num = 0;
    while (i < s.length && /\d/.test(s[i])) num = num * 10 + +s[i++];
    const node = { val: sign * num, left: null, right: null };
    if (s[i] === '(') { i++; node.left = parse(); i++; }   // skip '(' and ')'
    if (s[i] === '(') { i++; node.right = parse(); i++; }
    return node;
  };
  return s ? parse() : null;
}
Convert a binary tree to a doubly linked list (in-order)Medium1 approach

Problem

Convert the tree into a doubly linked list in place, using left as prev and right as next, so that the list follows the in-order sequence. Return the head.

Example 1

Input:  10 with left 12 (children 25, 30) and right 15 (left 36)
Output: 25 ⇄ 12 ⇄ 30 ⇄ 10 ⇄ 36 ⇄ 15

Also asked as: Convert Binary tree into Doubly Linked List

1. In-order traversal, stitch prev ↔ current

Time O(n)Space O(h)

Do an in-order walk keeping a `prev` pointer; set prev.right = cur and cur.left = prev. The first visited node is the DLL head.

function treeToDLL(root) {
  let head = null, prev = null;
  const inorder = (n) => {
    if (!n) return;
    inorder(n.left);
    if (prev) { prev.right = n; n.left = prev; }
    else head = n;
    prev = n;
    inorder(n.right);
  };
  inorder(root);
  return head;
}
Convert a binary tree to a sum tree / check if it is a sum treeMedium1 approach

Problem

(1) Convert: replace each node's value with the sum of all values in its left and right subtrees (the original values); leaves become 0. (2) Check: return true if every non-leaf node already equals the sum of all nodes in its two subtrees.

Example 1

Input:  convert [10, -2, 6, 8, -4, 7, 5]
Output: [20, 4, 12, 0, 0, 0, 0]

Example 2

Input:  check [26, 10, 3, 4, 6, null, 3]
Output: true

Also asked as: Convert Binary tree into Sum tree · Check if Binary tree is Sum tree or not

1. Post-order: replace with children sum / verify equality

Time O(n)Space O(h)

Convert: return oldValue + newLeft + newRight, set node.val to newLeft + newRight. Check: a node is valid iff its value equals the sum of both subtrees (leaves count as valid).

function toSumTree(node) {
  if (!node) return 0;
  const old = node.val;
  node.val = toSumTree(node.left) + toSumTree(node.right);
  return node.val + old;
}
function isSumTree(node) {
  if (!node || (!node.left && !node.right)) return true;
  const treeSum = (n) => (n ? n.val + treeSum(n.left) + treeSum(n.right) : 0);
  return node.val === treeSum(node.left) + treeSum(node.right) &&
    isSumTree(node.left) && isSumTree(node.right);
}
LCA, distance between two nodes, and Kth ancestor in a binary treeMedium1 approach

Problem

Three related queries on a binary tree: (1) the lowest common ancestor of two nodes; (2) the number of edges between two nodes, which is depth(a) + depth(b) − 2·depth(LCA); (3) the kth ancestor of a node, or −1 if the node is fewer than k levels deep.

Example 1

Input:  root = [1, 2, 3, 4, 5, 6, 7]: dist(4, 5), dist(4, 6), 2nd ancestor of 4
Output: 2, 4, 1

Also asked as: Find LCA in a Binary tree · Find distance between 2 nodes in a Binary tree · Kth Ancestor of node in a Binary tree

1. LCA via post-order; distance from depths; ancestor by path

Time O(n)Space O(h)

LCA: the node where the two targets first split. Distance(a,b) = depth(a) + depth(b) − 2·depth(LCA). Kth ancestor: record the root→node path, then step back k.

function lca(root, p, q) {
  if (!root || root.val === p || root.val === q) return root;
  const L = lca(root.left, p, q);
  const R = lca(root.right, p, q);
  return L && R ? root : L || R;
}
function distance(root, a, b) {
  const depth = (n, target, d = 0) => {
    if (!n) return -1;
    if (n.val === target) return d;
    const l = depth(n.left, target, d + 1);
    return l !== -1 ? l : depth(n.right, target, d + 1);
  };
  const anc = lca(root, a, b);
  return depth(anc, a, 0) + depth(anc, b, 0);
}
function kthAncestor(root, node, k) {
  const path = [];
  const find = (n) => {
    if (!n) return false;
    path.push(n);
    if (n.val === node || find(n.left) || find(n.right)) return true;
    path.pop();
    return false;
  };
  find(root);
  return path.length > k ? path[path.length - 1 - k].val : -1;
}
Path sums — longest root-to-leaf sum, largest subtree sum, max non-adjacent sum, K-sum pathsMedium4 approaches

Problem

Four sum problems on a binary tree:

Sum of the longest root-to-leaf path — if two paths are equally long, take the larger sum. Largest subtree sum — the maximum sum of any node plus all its descendants. Maximum non-adjacent sum — pick nodes to maximise the sum, never picking both a parent and its child (House Robber III). K-sum paths — count the downward paths (starting and ending anywhere) whose values sum to k.

Example 1

Input:  K-sum: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], k = 8
Output: 3

5→3, 5→2→1 and −3→11.

Also asked as: Sum of Nodes on the Longest path from root to leaf node · Find Largest subtree sum in a tree · Maximum Sum of nodes in Binary tree such that no two are adjacent · Print all "K" Sum paths in a Binary tree

1. Longest root-to-leaf path sum

Time O(n)Space O(h)

DFS returning (length, sum) of the best path; prefer the longer, break ties by larger sum.

function longestPathSum(root) {
  const dfs = (n) => {
    if (!n) return [0, 0];
    const [ll, ls] = dfs(n.left);
    const [rl, rs] = dfs(n.right);
    if (ll > rl || (ll === rl && ls >= rs)) return [ll + 1, ls + n.val];
    return [rl + 1, rs + n.val];
  };
  return dfs(root)[1];
}

2. Largest subtree sum

Time O(n)Space O(h)

Post-order; each node returns its subtree sum, and a running global max is updated.

function largestSubtreeSum(root) {
  let best = -Infinity;
  const sum = (n) => {
    if (!n) return 0;
    const s = n.val + sum(n.left) + sum(n.right);
    best = Math.max(best, s);
    return s;
  };
  sum(root);
  return best;
}

3. Max sum with no two adjacent (tree house robber)

Time O(n)Space O(h)

DFS returns [withNode, withoutNode]. withNode = n.val + left.without + right.without; without = max(left) + max(right).

function maxNonAdjacent(root) {
  const dfs = (n) => {
    if (!n) return [0, 0];
    const [lw, lwo] = dfs(n.left);
    const [rw, rwo] = dfs(n.right);
    return [n.val + lwo + rwo, Math.max(lw, lwo) + Math.max(rw, rwo)];
  };
  return Math.max(...dfs(root));
}

4. Print all downward paths summing to K

Time O(n·h)Space O(h)

Carry the path from root; at each node, walk the path backward adding values and print any suffix that sums to K.

function kSumPaths(root, k) {
  const path = [], res = [];
  const dfs = (n) => {
    if (!n) return;
    path.push(n.val);
    let sum = 0;
    for (let i = path.length - 1; i >= 0; i--) {
      sum += path[i];
      if (sum === k) res.push(path.slice(i));
    }
    dfs(n.left); dfs(n.right);
    path.pop();
  };
  dfs(root);
  return res;
}
Checks — leaves at same level, duplicate subtrees, is-a-tree (graph), min swaps to BSTMedium3 approaches

Problem

Four checks:

All leaves at the same level? Does the tree contain two identical subtrees with 2 or more nodes (find all duplicate subtrees)? Is an undirected graph a tree — connected, with no cycle? Minimum swaps to turn a complete binary tree (given as an array) into a BST — this is the minimum number of swaps to sort its in-order sequence.

Example 1

Input:  min swaps: [5, 6, 7, 8, 9, 10, 11]
Output: 3

In-order is [8, 6, 9, 5, 10, 7, 11]; sorting it takes 3 swaps.

Also asked as: Check if all leaf nodes are at same level or not · Check if a Binary Tree contains duplicate subtrees of size 2 or more · Find all Duplicate subtrees in a Binary tree · Check if given graph is tree or not · Find minimum swaps required to convert a Binary tree into BST

1. All leaves at the same level

Time O(n)Space O(h)

DFS tracking depth; record the first leaf’s depth and require every other leaf to match.

function leavesSameLevel(root) {
  let leafDepth = -1;
  const dfs = (n, d) => {
    if (!n) return true;
    if (!n.left && !n.right) {
      if (leafDepth === -1) leafDepth = d;
      return d === leafDepth;
    }
    return dfs(n.left, d + 1) && dfs(n.right, d + 1);
  };
  return dfs(root, 0);
}

2. Duplicate subtrees — serialize and count

Time O(n²) worst (string sizes), O(n) with idsSpace O(n)

Post-order serialize each subtree to a string; the first time a serialization repeats, that subtree is a duplicate.

function findDuplicateSubtrees(root) {
  const seen = new Map(), res = [];
  const ser = (n) => {
    if (!n) return '#';
    const s = n.val + ',' + ser(n.left) + ',' + ser(n.right);
    seen.set(s, (seen.get(s) || 0) + 1);
    if (seen.get(s) === 2) res.push(n);
    return s;
  };
  ser(root);
  return res;
}

3. Is an undirected graph a tree?

Time O(V + E)Space O(V + E)

A graph with n nodes is a tree iff it has exactly n−1 edges and is connected (one DFS/BFS component, no back-edge to a non-parent).

function isGraphTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  const seen = new Array(n).fill(false);
  const stack = [0];
  seen[0] = true;
  let count = 1;
  while (stack.length) {
    const u = stack.pop();
    for (const v of adj[u]) if (!seen[v]) { seen[v] = true; count++; stack.push(v); }
  }
  return count === n;
}

Min swaps to convert a binary tree to a BST: take the tree’s inorder array, then count minimum swaps to sort it (cycle decomposition — see "Minimum swaps to sort an array").

Check if all levels of two trees are anagramsEasy1 approach

Problem

Given two binary trees, return true if, for every level, the multiset of values on that level is the same in both trees.

Example 1

Input:  tree1 = [1, 3, 2, 5, 4], tree2 = [1, 2, 3, 4, 5]
Output: true

Also asked as: Check if all levels of two trees are anagrams or not

1. Level-order both trees, compare sorted level values

Time O(n log n)Space O(width)

BFS each tree level by level; two levels are anagrams iff their multisets of values match.

function levelsAreAnagrams(a, b) {
  let qa = a ? [a] : [], qb = b ? [b] : [];
  while (qa.length && qb.length) {
    if (qa.length !== qb.length) return false;
    const va = qa.map((n) => n.val).sort((x, y) => x - y);
    const vb = qb.map((n) => n.val).sort((x, y) => x - y);
    if (va.join(',') !== vb.join(',')) return false;
    const na = [], nb = [];
    for (const n of qa) { if (n.left) na.push(n.left); if (n.right) na.push(n.right); }
    for (const n of qb) { if (n.left) nb.push(n.left); if (n.right) nb.push(n.right); }
    qa = na; qb = nb;
  }
  return qa.length === 0 && qb.length === 0;
}
Same TreeEasy1 approach

Problem

Return true if two binary trees have the same structure and the same value at every node.

Example 1

Input:  p = [1, 2, 3], q = [1, 2, 3]
Output: true

Example 2

Input:  p = [1, 2], q = [1, null, 2]
Output: false

1. Parallel recursion

Time O(n)Space O(h)

Both empty → same; one empty or values differ → different; else compare children.

function isSameTree(p, q) {
  if (!p || !q) return p === q;
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Subtree of Another Tree reuses this at every node of the larger tree.

Path Sum IIMedium1 approach

Problem

Return every root-to-leaf path whose node values sum to targetSum, each as a list of values.

Example 1

Input:  root = [5,4,8,11,null,13,4,7,2,null,null,5,1], target = 22
Output: [[5,4,11,2], [5,8,4,5]]

1. DFS with a path (backtracking)

Time O(n²) worst case — copying pathsSpace O(h)

Push the node, subtract its value; at a leaf with remaining 0 record a copy; pop on the way back.

function pathSum(root, target) {
  const res = [], path = [];
  const dfs = (node, rem) => {
    if (!node) return;
    path.push(node.val);
    rem -= node.val;
    if (!node.left && !node.right && rem === 0) res.push([...path]);
    dfs(node.left, rem);
    dfs(node.right, rem);
    path.pop();
  };
  dfs(root, target);
  return res;
}
Count Good Nodes in Binary TreeMedium1 approach

Problem

A node is good if no node on the path from the root to it has a greater value. Return the number of good nodes.

Example 1

Input:  [3, 1, 4, 3, null, 1, 5]
Output: 4

Nodes 3 (root), 4, 5 and the lower 3.

1. DFS carrying the path maximum

Time O(n)Space O(h)

A node is good if its value ≥ the maximum seen from the root to it.

function goodNodes(root) {
  const dfs = (node, max) => {
    if (!node) return 0;
    const good = node.val >= max ? 1 : 0;
    max = Math.max(max, node.val);
    return good + dfs(node.left, max) + dfs(node.right, max);
  };
  return dfs(root, -Infinity);
}
Binary Tree Maximum Path SumHard1 approach

Problem

A path is any sequence of connected nodes (going up and then down at most once), with no node repeated; it need not pass through the root. Return the largest sum of any non-empty path. Values can be negative.

Example 1

Input:  [1, 2, 3]
Output: 6

Example 2

Input:  [-10, 9, 20, null, null, 15, 7]
Output: 42

15 → 20 → 7.

1. Post-order: return best downward gain, update global best

Time O(n)Space O(h)

At each node, the path that bends here is val + left gain + right gain (gains clipped at 0). Only one side can continue upward, so return val + max(gain).

function maxPathSum(root) {
  let best = -Infinity;
  const gain = (node) => {
    if (!node) return 0;
    const l = Math.max(0, gain(node.left));
    const r = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + l + r);
    return node.val + Math.max(l, r);
  };
  gain(root);
  return best;
}

Same shape as diameter: "answer through this node" differs from "value returned to parent".

Serialize and Deserialize Binary TreeHard1 approach

Problem

Design serialize(root) → string and deserialize(string) → root so that any binary tree survives the round trip unchanged. You choose the format.

Example 1

Input:  [1, 2, 3, null, null, 4, 5]
Output: deserialize(serialize(root)) gives the same tree

1. Pre-order with null markers

Time O(n)Space O(n)

Write values in pre-order with "#" for null. Reading back in the same order rebuilds the tree uniquely.

function serialize(root) {
  const out = [];
  const dfs = (n) => {
    if (!n) { out.push('#'); return; }
    out.push(n.val);
    dfs(n.left); dfs(n.right);
  };
  dfs(root);
  return out.join(',');
}


function deserialize(data) {
  const vals = data.split(',');
  let i = 0;
  const build = () => {
    const v = vals[i++];
    if (v === '#') return null;
    const node = new TreeNode(Number(v));
    node.left = build();
    node.right = build();
    return node;
  };
  return build();
}

BFS level order with nulls (LeetCode’s own format) also works; mention the choice.