DSA for Interviews, From Zero

Part 11 · Lesson 43 · read

DFS on Trees

Height, balance, diameter (the longest path) and path sums.

On this page

  1. The mindset: return a value up the tree
  2. Height, the model problem
  3. Balanced tree and the -1 trick
  4. Diameter: record one thing, return another
  5. Traced: diameter of a small tree
  6. Path sum: passing a value down
  7. Maximum path sum (the hard one)
  8. Symmetric tree and subtree of another tree
  9. Practice questions (7)
  10. Make it stick
  11. What's next

The mindset: return a value up the tree

Lesson 41 introduced binary trees and walking them with recursion. Lesson 42 visited them row by row with a queue. This lesson uses depth-first search (DFS) to answer questions about a whole tree. DFS means going all the way down one branch, then backing up to try the next branch.

Two terms to keep in mind. A binary tree is a set of nodes where each node has at most two children, a left child and a right child. The top node is the root. Recursion means a function that solves a problem by calling itself on a smaller piece of the same problem. On a tree, the smaller pieces are the left and right subtrees (a subtree is a node together with everything below it).

The trick is a way of thinking. A tree is a node with two smaller trees hanging off it. So to answer a question about a tree, pretend the recursive call already gave the answer for the left side and the right side. Then join those two answers with the current node to make your own answer. Return that answer to the parent. Every tree function has the same three parts:

  1. Base case. What is the answer for an empty tree (null)? This simple answer stops the recursion.
  2. Recurse. Call the function on the left child and the right child. Trust the answers. Do not try to follow them in your head.
  3. Combine. Use the two answers and node.val to make the answer for this node.

The answer travels from the leaves up to the root, so this style is called bottom-up. The opposite is to pass information down as extra arguments. We do that for path sum. Many problems need both. Start by asking: "what one value should a node give to its parent?" (The difference in one line: bottom-up sends answers up from the children, and top-down sends information down to the children.)

All samples below build their tree with a small helper called buildTree. It reads a level-order array (the tree row by row, from the top row down, and each row from left to right), where null marks a missing child. LeetCode uses the same format. Each sample is complete on its own, so you can paste it into a file and run it.

Height, the model problem

The height of a tree is the number of nodes on the longest path from the root down to a leaf (a leaf is a node with no children). An empty tree has height 0. A tree with one node has height 1. Some books count edges (the links between nodes) instead, so a single node has height 0 there. LeetCode's "maximum depth" counts nodes, and so do we.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function height(node) {  if (node === null) return 0;              // base case: an empty tree has height 0  const left = height(node.left);           // trust the recursion: height of the left subtree  const right = height(node.right);         // ... and of the right subtree  return 1 + Math.max(left, right);         // combine: this node adds one level}console.log(height(buildTree([3, 9, 20, null, null, 15, 7]))); // 3console.log(height(buildTree([1, 2, null, 3])));               // 3console.log(height(buildTree([])));                            // 0

Read it with the three parts in mind. The base case is 0. We trust height(node.left) and height(node.right). We combine them as "the taller side, plus this node". Time is O(n) (the work grows in step with the number of nodes n), because each node is visited once. Extra space is O(h) for the recursion stack (the pile of calls that have started but not finished), where h is the height. For a bushy tree h is about log n. For a tree that is one long chain, h can be as big as n.

Depth versus height
Depth is how far a node is below the root (the root has depth 0 or 1, depending on the book). Height is how far the deepest leaf is below a node. Information that flows up is a height. Information that flows down is a depth.

Balanced tree and the -1 trick

A tree is height-balanced if, at every node, the heights of the left side and the right side differ by at most 1. The simple way is to check each node by working out both heights from scratch:

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function height(node) {  if (node === null) return 0;  return 1 + Math.max(height(node.left), height(node.right));}// Top-down: at every node, compute both heights from scratch, then ask the children too.function isBalancedSlow(node) {  if (node === null) return true;  if (Math.abs(height(node.left) - height(node.right)) > 1) return false;  return isBalancedSlow(node.left) && isBalancedSlow(node.right);}console.log(isBalancedSlow(buildTree([3, 9, 20, null, null, 15, 7])));          // trueconsole.log(isBalancedSlow(buildTree([1, 2, 2, 3, 3, null, null, 4, 4])));      // false

This works, but height is worked out again and again for the same nodes. On a tree shaped like a chain, each node starts a walk down everything below it. That takes O(n²) time. (On a perfectly bushy tree it is only O(n log n).)

The fix is to do both jobs in one walk. The function returns the height as usual. But if it finds an unbalanced node, it returns the special value -1 instead. A special value that works as a warning signal is called a sentinel (like a guard that raises an alarm). A height is never negative, so -1 cannot be mistaken for a real height. Every parent just passes the -1 straight up.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isBalanced(root) {  // Returns the height of the subtree, or -1 as soon as any subtree is unbalanced.  function check(node) {    if (node === null) return 0;    const left = check(node.left);    if (left === -1) return -1;             // a problem below: pass it straight up    const right = check(node.right);    if (right === -1) return -1;    if (Math.abs(left - right) > 1) return -1;   // this node is the problem    return 1 + Math.max(left, right);  }  return check(root) !== -1;}console.log(isBalanced(buildTree([3, 9, 20, null, null, 15, 7])));          // trueconsole.log(isBalanced(buildTree([1, 2, 2, 3, 3, null, null, 4, 4])));      // falseconsole.log(isBalanced(buildTree([])));                                      // true

Now each node is visited once: O(n) time, O(h) space. Remember this pattern: when a part of the tree can fail, let the returned value carry the failure upward.

Diameter: record one thing, return another

The diameter of a tree is the length (counted in edges, the links between nodes) of the longest path between any two nodes. The path does not have to pass through the root. Look at the highest node on the path. This is where the path "turns". From there it goes down the left side as far as it can, and down the right side as far as it can. So the length of the path through that node is leftHeight + rightHeight.

Here is the idea that confuses many people. It also appears in the hardest problem of this lesson. The function returns one thing but records another thing:

  • It records the best path that turns at this node (using both sides). It saves this in a variable that lives outside the recursion, often called a global best. Here it is a variable of the outer function, and the inner function can update it.
  • It returns only the height (using one side). A parent can continue only one branch upward, because a path cannot split into two.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function diameterOfBinaryTree(root) {  let best = 0;                              // the answer: the longest path seen at any node  function height(node) {    if (node === null) return 0;    const left = height(node.left);    const right = height(node.right);    best = Math.max(best, left + right);     // RECORD: the longest path that turns at this node    return 1 + Math.max(left, right);        // RETURN: only one side can continue upward  }  height(root);  return best;}console.log(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])));   // 3console.log(diameterOfBinaryTree(buildTree([1, 2])));            // 1console.log(diameterOfBinaryTree(buildTree([1])));               // 0
Dry run · the pattern shared by the four problems so far
ProblemReturns to the parentRecords in the outer variable
height1 + max(left, right)nothing
balanced treethe height, or -1 on failurenothing (the -1 carries the failure)
diameter1 + max(left, right)left + right at every node
maximum path sumnode + the better one-sided gainnode + both gains at every node

When a question says 'any path' that can turn at its top node, expect this split: one thing recorded, another thing returned.

Traced: diameter of a small tree

Step through the diameter on the tree [1, 2, 3, 4, 5]. Watch the order. The code goes all the way down to the leftmost leaf first. Values start to flow back up only after the recursion reaches empty children.

step 1 / 19
Set up
best = 0

best remembers the longest path found so far. We count the path in edges (links between nodes). The tree is: 1 has children 2 and 3, and 2 has children 4 and 5.

▶let best = 0;2function height(node) {3  if (node === null) {4    return 0;5  }6  const left = height(node.left);7  const right = height(node.right);8  best = Math.max(best, left + right);9  return 1 + Math.max(left, right);10}11height(root);12console.log(best);
Variables
best0
Console
(nothing printed yet)
The best path turns at the root: two levels down the left side (via 2) plus one level down the right side gives 3 edges. Each node returns only its height, never the path that turns. · interactive

Path sum: passing a value down

Does some path from the root to a leaf add up to the target? Here the information travels down. At each node, subtract node.val from the target and give what is left to the children. At a leaf, what is left must equal the value of the leaf.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function hasPathSum(node, target) {  if (node === null) return false;                       // no tree, no path  if (node.left === null && node.right === null) {       // a leaf: the path must end here    return node.val === target;  }  const rest = target - node.val;                        // pass the remaining sum DOWN  return hasPathSum(node.left, rest) || hasPathSum(node.right, rest);}const tree = buildTree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]);console.log(hasPathSum(tree, 22)); // true  (5 + 4 + 11 + 2)console.log(hasPathSum(tree, 26)); // true  (5 + 8 + 13)console.log(hasPathSum(tree, 5));  // false (5 is not a leaf)
The leaf check matters
The path must end at a leaf. Suppose you only test node.val === target at every node. Then a target of 5 would be "found" at the root of the example. That is wrong, because the root has children. Also, values can be negative. So you cannot stop early just because what is left drops below zero.

Maximum path sum (the hard one)

Now we use everything together. A path is any chain of connected nodes that never visits a node twice. It can start and end anywhere. It does not need to touch the root or a leaf. Find the largest sum of node values on such a path. Values can be negative.

It is the diameter pattern, but with sums instead of lengths:

  • gain(node) is the best sum of a path that starts at node and goes down one side only. We return this.
  • The best path that turns at node is node.val + leftGain + rightGain. We record this.
  • A negative gain only makes the sum smaller, so we replace it with 0. That means "do not go that way". Math.max(0, ...) does this.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function maxPathSum(root) {  let best = -Infinity;                      // values can be negative, so do not start at 0  // Returns the best sum of a path that starts at "node" and goes DOWN one side only.  function gain(node) {    if (node === null) return 0;    const left = Math.max(0, gain(node.left));     // a negative branch is better left out    const right = Math.max(0, gain(node.right));    best = Math.max(best, node.val + left + right);   // RECORD: a path that turns at this node    return node.val + Math.max(left, right);          // RETURN: go on upward through one side only  }  gain(root);  return best;}console.log(maxPathSum(buildTree([1, 2, 3])));                       // 6console.log(maxPathSum(buildTree([-10, 9, 20, null, null, 15, 7])));  // 42console.log(maxPathSum(buildTree([-3])));                            // -3
Dry run · tree [-10, 9, 20, null, null, 15, 7]
NodeLeft gainRight gainPath that turns here (recorded)Returned
90099
15001515
70077
2015720 + 15 + 7 = 4220 + 15 = 35
-10935-10 + 9 + 35 = 34-10 + 35 = 25

The best recorded value is 42: the path 15 → 20 → 7. The function never returns this answer. That is why we need the outer variable.

O(n) time, O(h) space. There are two classic mistakes. The first is to start best at 0. A tree with only negative values must answer with its largest value, the one closest to zero, like -3 above. The second is to return the path that turns instead of the one-sided gain. Then the parent would add a path that splits in two.

Symmetric tree and subtree of another tree

Both of these compare two trees at once. So the recursive function takes two nodes and walks them together.

A tree is symmetric if its left half is the mirror image of its right half. Two trees a and b are mirrors when three things are true. Their root values match. The left side of a mirrors the right side of b. The right side of a mirrors the left side of b. The crossing over is the whole idea.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSymmetric(root) {  // Are the trees a and b mirror images of each other?  function mirror(a, b) {    if (a === null && b === null) return true;    if (a === null || b === null) return false;    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);  }  return root === null || mirror(root.left, root.right);}console.log(isSymmetric(buildTree([1, 2, 2, 3, 4, 4, 3])));        // trueconsole.log(isSymmetric(buildTree([1, 2, 2, null, 3, null, 3])));  // false

For subtree of another tree, we first write isSameTree(a, b). It is the same walk but without crossing: left with left, and right with right. Then we try it at every node of the big tree:

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSameTree(a, b) {  if (a === null && b === null) return true;  if (a === null || b === null) return false;  return a.val === b.val && isSameTree(a.left, b.left) && isSameTree(a.right, b.right);}function isSubtree(root, subRoot) {  if (root === null) return subRoot === null;  return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}console.log(isSubtree(buildTree([3, 4, 5, 1, 2]), buildTree([4, 1, 2])));                                // trueconsole.log(isSubtree(buildTree([3, 4, 5, 1, 2, null, null, null, null, 0]), buildTree([4, 1, 2])));     // false

Each call of isSameTree costs up to the size of the smaller tree. We try it at up to n nodes. So the total is O(m · n) for trees with n and m nodes. That is fine for interview limits. A faster way is to turn each tree into a string (a line of text) and check whether one string is a substring of the other (a piece of text found inside the longer text). Question 6 shows how, and the separator trap you must avoid.

Practice questions

For each question, say aloud: "What does my function return to the parent? Does it also need to record something else?"

Q1Balanced binary treeEasy

A binary tree is height-balanced if, at every node, the heights of its left side and right side differ by at most 1. Return whether the given tree is height-balanced.

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: true
Explanation: At every node, the heights of the left side and the right side differ by at most 1.
Example 2
Input: root = [1, 2, 2, 3, 3, null, null, 4, 4]
Output: false
Explanation: The left child of the root has height 3, but the right child has height 1. The difference is 2.
Example 3
Input: root = []
Output: true
Explanation: An empty tree is balanced.
Stuck? Open one hint at a time
Hint 1
"Balanced" must hold at every node, not only at the root.
Hint 2
If you call a separate height function at each node, how many times do you visit the same node?
Hint 3
Let one function do both jobs. Return the height as usual. Return -1 as a warning signal when something below is unbalanced.
Show all 2 solutions with explanations
Approach 1Brute force: recompute heights at every node
The idea
  1. Write height(node).
  2. At each node, compare the heights of its left side and right side.
  3. Call the function on both children. They must be balanced too.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isBalanced(root) {  function height(node) {    if (node === null) return 0;    return 1 + Math.max(height(node.left), height(node.right));  }  if (root === null) return true;  if (Math.abs(height(root.left) - height(root.right)) > 1) return false;  return isBalanced(root.left) && isBalanced(root.right);}console.log(isBalanced(buildTree([3, 9, 20, null, null, 15, 7])));          // trueconsole.log(isBalanced(buildTree([1, 2, 2, 3, 3, null, null, 4, 4])));      // false
How it works

Correct, but every ancestor (the parent, the grandparent, and so on) walks the same nodes again with its own height call. It takes O(n log n) on a bushy tree and O(n²) on a tree shaped like a chain.

Approach 2Bottom-up with a -1 warning value (sentinel)
The idea
  1. Return the height of this part of the tree, or -1 if anything below it is unbalanced.
  2. If either child returns -1, pass -1 up at once.
  3. If the two heights differ by more than 1, return -1. Otherwise return the height.
  4. The tree is balanced when the root does not return -1.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isBalanced(root) {  function check(node) {    if (node === null) return 0;    const left = check(node.left);    if (left === -1) return -1;    const right = check(node.right);    if (right === -1) return -1;    if (Math.abs(left - right) > 1) return -1;    return 1 + Math.max(left, right);  }  return check(root) !== -1;}console.log(isBalanced(buildTree([3, 9, 20, null, null, 15, 7])));          // trueconsole.log(isBalanced(buildTree([1, 2, 2, 3, 3, null, null, 4, 4])));      // falseconsole.log(isBalanced(buildTree([])));                                      // true
How it works

Each node is visited once, so the time is O(n) and the space for the recursion is O(h). The first problem it finds travels straight up to the root.

Which approach should you use?

Use the -1 version. Interviewers expect it. Mention the slow version first as your starting point. Then explain how you removed the repeated work. (LeetCode 110.)

Q2Diameter of binary treeEasy

Return the length of the longest path between any two nodes in the tree, measured in edges. The path may pass through the root, or it may not.

Example 1
Input: root = [1, 2, 3, 4, 5]
Output: 3
Explanation: The path 4 → 2 → 1 → 3 has three edges.
Example 2
Input: root = [1, 2]
Output: 1
Explanation: There is one edge between the two nodes.
Example 3
Input: root = [1]
Output: 0
Explanation: A single node has no edges.
Stuck? Open one hint at a time
Hint 1
Look at the highest node of the longest path. The path goes down its left side and also down its right side.
Hint 2
Its length in edges is the height of the left side plus the height of the right side (heights counted in nodes).
Hint 3
The function you call recursively returns a height. But the answer is the largest left + right seen at any node.
Show all 2 solutions with explanations
Approach 1Brute force: find the height of both sides at every node
The idea

For every node, compute the heights of its two subtrees with a separate height function, take the sum, and keep the maximum over all nodes.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function diameterOfBinaryTree(root) {  function height(node) {    if (node === null) return 0;    return 1 + Math.max(height(node.left), height(node.right));  }  if (root === null) return 0;  const through = height(root.left) + height(root.right);  return Math.max(through, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));}console.log(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5]))); // 3console.log(diameterOfBinaryTree(buildTree([1, 2])));          // 1
How it works

Correct, but each height call walks a whole part of the tree again. The worst case is O(n²).

Approach 2One pass: record left + right, return the height
The idea
  1. Call the function on both children to get their heights.
  2. Update the outer variable best with left + right.
  3. Return 1 + max(left, right) to the parent.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function diameterOfBinaryTree(root) {  let best = 0;  function height(node) {    if (node === null) return 0;    const left = height(node.left);    const right = height(node.right);    best = Math.max(best, left + right);    return 1 + Math.max(left, right);  }  height(root);  return best;}console.log(diameterOfBinaryTree(buildTree([1, 2, 3, 4, 5])));   // 3console.log(diameterOfBinaryTree(buildTree([1, 2])));            // 1console.log(diameterOfBinaryTree(buildTree([1])));               // 0
How it works

O(n) time, O(h) space. The returned value (height) and the recorded value (the bent path) are different, which is exactly why a plain recursion that returns the answer does not work.

Which approach should you use?

Use the one-pass version. The brute force is a good starting point to say out loud, but it repeats work. (LeetCode 543.)

Q3Path sumEasy

Given a tree and an integer targetSum, return true if there is a root-to-leaf path whose node values add up to targetSum. Values may be negative.

Example 1
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Output: true
Explanation: 5 → 4 → 11 → 2 adds up to 22 and ends at a leaf.
Example 2
Input: root = [1, 2, 3], targetSum = 5
Output: false
Explanation: The sums from the root to the leaves are 3 and 4.
Example 3
Input: root = [], targetSum = 0
Output: false
Explanation: An empty tree has no path from the root to a leaf.
Stuck? Open one hint at a time
Hint 1
Pass what is left of the target down. Subtract the value of the node before you go to the children.
Hint 2
The path must end at a leaf. How can you tell that a node is a leaf?
Show all 3 solutions with explanations
Approach 1Brute force: collect the sum of every root-to-leaf path
The idea

Walk the tree and add the values along the way. At each leaf, add the total to a list. At the end, check whether the target is in the list.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function hasPathSum(root, targetSum) {  const sums = [];  function walk(node, running) {    if (node === null) return;    running += node.val;    if (node.left === null && node.right === null) sums.push(running);    walk(node.left, running);    walk(node.right, running);  }  walk(root, 0);  return sums.includes(targetSum);}console.log(hasPathSum(buildTree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]), 22)); // trueconsole.log(hasPathSum(buildTree([1, 2, 3]), 5));                                               // false
How it works

O(n) time, but O(n) extra space for the list. It also keeps going after the answer is already known.

Approach 2Recursion: subtract on the way down
The idea
  1. Empty tree: return false.
  2. Leaf: return whether its value equals what is left of the target.
  3. Otherwise: return true if either child can finish the rest of the sum.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function hasPathSum(root, targetSum) {  if (root === null) return false;  if (root.left === null && root.right === null) return root.val === targetSum;  const rest = targetSum - root.val;  return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);}console.log(hasPathSum(buildTree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]), 22)); // trueconsole.log(hasPathSum(buildTree([1, 2, 3]), 5));                                               // falseconsole.log(hasPathSum(buildTree([]), 0));                                                      // false
How it works

O(n) time, O(h) space. The || stops as soon as one path works.

Approach 3DFS with your own stack (no recursion)
The idea

Replace the recursion with a stack (a pile where the last item added is the first one taken out) of [node, sum so far] pairs. Pop one pair and add its value. At a leaf, check the target. Otherwise push the children.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function hasPathSum(root, targetSum) {  if (root === null) return false;  const stack = [[root, 0]];  while (stack.length) {    const [node, sum] = stack.pop();    const total = sum + node.val;    if (node.left === null && node.right === null && total === targetSum) return true;    if (node.right) stack.push([node.right, total]);    if (node.left) stack.push([node.left, total]);  }  return false;}console.log(hasPathSum(buildTree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]), 22)); // trueconsole.log(hasPathSum(buildTree([1, 2, 3]), 5));                                               // false
How it works

The time is the same, O(n). It helps when a very deep tree could overflow the call stack (run out of room for open calls).

Which approach should you use?

The recursion is the shortest and clearest. Mention the stack version if the interviewer asks about very deep trees. (LeetCode 112.)

Q4Binary tree maximum path sumHard

A path is a chain of connected nodes where each node appears at most once. It does not have to pass through the root or end at a leaf. Return the largest sum of node values over all paths that have at least one node. Values may be negative.

Example 1
Input: root = [1, 2, 3]
Output: 6
Explanation: The path 2 → 1 → 3.
Example 2
Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42
Explanation: The path 15 → 20 → 7. It does not touch the root.
Example 3
Input: root = [-3]
Output: -3
Explanation: A path needs at least one node, so the answer can be negative.
Stuck? Open one hint at a time
Hint 1
Look at the highest node of the path. The path goes down its left side and down its right side.
Hint 2
Define gain(node) as the best sum of a path that starts at the node and goes down one side only. A parent can use only this.
Hint 3
If the gain of a child is negative, ignore it (use 0).
Hint 4
Start the global best at -Infinity (smaller than any number), not at 0.
Show all 2 solutions with explanations
Approach 1Brute force: try every node as the top
The idea

For every node, work out the best downward gain of its left side and right side separately, with a helper function. Combine them as node.val + left + right. Take the largest result over all nodes.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function maxPathSum(root) {  // Best downward path starting at node (always includes node).  function down(node) {    if (node === null) return 0;    return node.val + Math.max(0, down(node.left), down(node.right));  }  let best = -Infinity;  function visit(node) {    if (node === null) return;    const through = node.val + Math.max(0, down(node.left)) + Math.max(0, down(node.right));    best = Math.max(best, through);    visit(node.left);    visit(node.right);  }  visit(root);  return best;}console.log(maxPathSum(buildTree([1, 2, 3])));                       // 6console.log(maxPathSum(buildTree([-10, 9, 20, null, null, 15, 7])));  // 42
How it works

Correct, but down walks the same nodes again for every ancestor. It takes O(n²) on a skewed tree (a tree that leans to one side, like a chain).

Approach 2One pass: record the path that turns, return the one-sided gain
The idea
  1. gain(node) returns the best path sum that starts at the node and goes down one side only.
  2. Replace a left or right gain below 0 with 0.
  3. Update the global best with node.val + left + right.
  4. Return node.val + max(left, right).
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function maxPathSum(root) {  let best = -Infinity;  function gain(node) {    if (node === null) return 0;    const left = Math.max(0, gain(node.left));    const right = Math.max(0, gain(node.right));    best = Math.max(best, node.val + left + right);    return node.val + Math.max(left, right);  }  gain(root);  return best;}console.log(maxPathSum(buildTree([1, 2, 3])));                       // 6console.log(maxPathSum(buildTree([-10, 9, 20, null, null, 15, 7])));  // 42console.log(maxPathSum(buildTree([-3])));                            // -3console.log(maxPathSum(buildTree([2, -1])));                         // 2
How it works

O(n) time, O(h) space. On [2, -1] the child's gain is clamped to 0, so the best path is just the root, 2. A path that forks (using both children and then continuing to a parent) is never counted, because only the one-sided gain is returned.

Which approach should you use?

Use the one-pass version. It has the same shape as diameter, but with sums, and a negative gain is replaced by 0. (LeetCode 124.)

Q5Symmetric treeEasy

Return whether a binary tree is a mirror image of itself (the same on both sides of its centre).

Example 1
Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true
Explanation: The left half is the mirror image of the right half.
Example 2
Input: root = [1, 2, 2, null, 3, null, 3]
Output: false
Explanation: Both 3s are on the right side of their parents. So they are not mirror images.
Stuck? Open one hint at a time
Hint 1
Compare two trees at once: the left side of the root and the right side of the root.
Hint 2
For mirrors, compare the left child of one with the right child of the other.
Show all 3 solutions with explanations
Approach 1Level by level: each row reads the same both ways
The idea

Write each level as a list of values, with null for gaps. For a mirror image, every level must read the same forwards and backwards.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSymmetric(root) {  let level = [root];  while (level.some((n) => n !== null)) {    const vals = level.map((n) => (n === null ? null : n.val));    for (let i = 0, j = vals.length - 1; i < j; i++, j--) {      if (vals[i] !== vals[j]) return false;    }    const next = [];    for (const n of level) if (n !== null) next.push(n.left, n.right);    level = next;  }  return true;}console.log(isSymmetric(buildTree([1, 2, 2, 3, 4, 4, 3])));        // trueconsole.log(isSymmetric(buildTree([1, 2, 2, null, 3, null, 3])));  // false
How it works

O(n) time and O(width) space (the width is the number of nodes in the widest row). It works because we write the gaps as null.

Approach 2Recursive mirror check
The idea
  1. Two nulls are mirrors. One null and one node are not mirrors.
  2. Otherwise the values must match. Also a.left must mirror b.right, and a.right must mirror b.left.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSymmetric(root) {  function mirror(a, b) {    if (a === null && b === null) return true;    if (a === null || b === null) return false;    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);  }  return root === null || mirror(root.left, root.right);}console.log(isSymmetric(buildTree([1, 2, 2, 3, 4, 4, 3])));        // trueconsole.log(isSymmetric(buildTree([1, 2, 2, null, 3, null, 3])));  // false
How it works

O(n) time, O(h) space.

Approach 3With a queue of pairs (no recursion)
The idea

Put the two children of the root in a queue (a line where the first item added is the first one taken out) as a pair. Take a pair, compare it, and add the crossed child pairs. Repeat.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSymmetric(root) {  if (root === null) return true;  const queue = [[root.left, root.right]];  while (queue.length) {    const [a, b] = queue.shift();    if (a === null && b === null) continue;    if (a === null || b === null || a.val !== b.val) return false;    queue.push([a.left, b.right], [a.right, b.left]);  }  return true;}console.log(isSymmetric(buildTree([1, 2, 2, 3, 4, 4, 3])));        // trueconsole.log(isSymmetric(buildTree([1, 2, 2, null, 3, null, 3])));  // false
How it works

It pairs nodes in the same way as the recursion, but without a call stack.

Which approach should you use?

Use the recursive mirror check. It is the shortest and shows the crossing idea best. (LeetCode 101.)

Q6Subtree of another treeEasy

Return true if subRoot has exactly the same shape and node values as some subtree of root. A subtree is a node of root together with all the nodes below it.

Example 1
Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true
Explanation: The part of the tree that starts at node 4 is identical to subRoot.
Example 2
Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output: false
Explanation: The part that starts at node 4 has an extra child (0) below the 2. So it is not identical.
Stuck? Open one hint at a time
Hint 1
Write a helper function that tells you whether two trees are exactly the same.
Hint 2
Use the helper at every node of the big tree.
Hint 3
A subtree includes all nodes below its top node (its descendants). Both trees must end at the same place.
Show all 2 solutions with explanations
Approach 1Compare at every node
The idea
  1. isSameTree(a, b) is true when both are null, or when the values are the same and the left sides are the same and the right sides are the same.
  2. For every node of root, check isSameTree(node, subRoot).
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSubtree(root, subRoot) {  function same(a, b) {    if (a === null && b === null) return true;    if (a === null || b === null) return false;    return a.val === b.val && same(a.left, b.left) && same(a.right, b.right);  }  if (root === null) return subRoot === null;  return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}console.log(isSubtree(buildTree([3, 4, 5, 1, 2]), buildTree([4, 1, 2])));                              // trueconsole.log(isSubtree(buildTree([3, 4, 5, 1, 2, null, null, null, null, 0]), buildTree([4, 1, 2])));   // false
How it works

O(m · n) time in the worst case (n nodes in root, m in subRoot), O(h) space. This is fine for the limits of the problem.

Approach 2Turn both trees into text and look for a substring
The idea

Turn each tree into a string with a preorder walk (visit the node first, then its left side, then its right side). Write a marker for every null. Then check whether the string of the small tree appears inside the string of the big tree. The markers make the shape clear. Each value is wrapped in brackets, so [2] can never match inside [12].

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isSubtree(root, subRoot) {  function serialize(node) {    if (node === null) return "[#]";    return "[" + node.val + "]" + serialize(node.left) + serialize(node.right);  }  return serialize(root).includes(serialize(subRoot));}console.log(isSubtree(buildTree([3, 4, 5, 1, 2]), buildTree([4, 1, 2])));                              // trueconsole.log(isSubtree(buildTree([3, 4, 5, 1, 2, null, null, null, null, 0]), buildTree([4, 1, 2])));   // falseconsole.log(isSubtree(buildTree([12]), buildTree([2])));                                                 // false
How it works

Building the strings is O(m + n). JavaScript's includes (which asks whether one string contains another) is not promised to be linear, so say "about O(m + n) with a good substring search". Without the brackets, tree [12] would wrongly contain [2]. Without the # markers, two trees with different shapes could give the same string.

Which approach should you use?

Start with the node-by-node comparison. It is easy to write correctly. Turning the trees into strings is a nice follow-up if the interviewer asks for a faster way. (LeetCode 572.)

Q7Path sum IIIMedium

Count the downward paths (going from parent to child, starting and ending at any node) whose node values add up to targetSum. Values may be negative.

Example 1
Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
Output: 3
Explanation: The paths 5 → 3, 5 → 2 → 1 and -3 → 11 all sum to 8.
Example 2
Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
Output: 3
Explanation: 5 → 4 → 11 → 2, 5 → 8 → 4 → 5 and 4 → 11 → 7 all sum to 22.
Stuck? Open one hint at a time
Hint 1
A path must go downward (from parent to child), but it can start and end at any node.
Hint 2
Brute force: treat every node as a possible start. Count the downward paths from it that add up to the target.
Hint 3
Remember the prefix-sum trick from arrays (a prefix sum is the running total of the values from the start up to here). Say the running sum from the root to here is S. Then a path that ends here with sum T exists for each earlier ancestor whose running sum was S − T.
Hint 4
Keep a map of the running sums on the current path from the root to this node. Undo your entry when you leave the node.
Show all 2 solutions with explanations
Approach 1Brute force: start a count at every node
The idea

For each node, run a DFS (depth-first search) downward and count how many paths from it reach the target. Then add up the counts for all nodes.

JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function pathSum(root, targetSum) {  function from(node, remaining) {          // paths that start exactly at node    if (node === null) return 0;    const here = node.val === remaining ? 1 : 0;    return here + from(node.left, remaining - node.val) + from(node.right, remaining - node.val);  }  if (root === null) return 0;  return from(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);}console.log(pathSum(buildTree([10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]), 8));            // 3console.log(pathSum(buildTree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]), 22));    // 3
How it works

You cannot stop early at a match, because values can be negative, so a longer path might also reach the target. It takes O(n²) on a chain and O(n log n) on a bushy tree.

Approach 2Prefix sums on the root-to-node path
The idea
  1. Keep running, the sum from the root to the current node. Also keep a Map (a table of key and value pairs) from each running sum to how many times it appears on the current path. Start with {0: 1} for the empty prefix (the path with no nodes).
  2. At a node, the number of paths that end here is map[running − target].
  3. Add the running sum of this node to the map. Call the function on both children. Then remove it again (this is called backtracking: undoing a step when you go back), so other branches do not see it.
JavaScript
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function pathSum(root, targetSum) {  const seen = new Map([[0, 1]]);            // running sum -> count on the current path  function dfs(node, running) {    if (node === null) return 0;    running += node.val;    let count = seen.get(running - targetSum) ?? 0;    seen.set(running, (seen.get(running) ?? 0) + 1);    count += dfs(node.left, running) + dfs(node.right, running);    seen.set(running, seen.get(running) - 1);   // backtrack when leaving this node    return count;  }  return dfs(root, 0);}console.log(pathSum(buildTree([10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]), 8));            // 3console.log(pathSum(buildTree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]), 22));    // 3console.log(pathSum(buildTree([1, -2, -3]), -1));                                            // 1
How it works

This is the "subarray sum equals k" trick, used on every path from the root to a node. O(n) time and O(h) space. Backtracking is a must: a running sum from one branch must not be counted by a node in a sibling branch (a branch next to it).

Which approach should you use?

Use the prefix-sum map for O(n). Offer the brute force first. It is a sensible answer for small trees. Then show how the prefix-sum idea from earlier lessons removes the repeated work. (LeetCode 437.)

Make it stick

Make it stick — close this page, then
  1. Name the three parts of a bottom-up tree function: base case, recurse, combine.
  2. Explain how returning -1 lets one walk check the balance, and why that is better than working out heights again and again.
  3. For diameter and maximum path sum, explain what is recorded and what is returned, and why they are different.
  4. Say why path sum must test for a leaf, and why a negative gain is replaced by 0.
  5. Say which children are paired in the mirror check, and why.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

So far a tree could hold any values in any order. Lesson 44 adds one rule: "smaller values go to the left, larger values go to the right". This gives us the binary search tree. You can search it, add to it and delete from it in about log n steps.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series