DSA for Interviews, From Zero

Part 11 · Lesson 45 · read

Lowest Common Ancestor and Building Trees

Find the lowest common ancestor in a binary tree and a BST. Build a tree again from its traversals.

On this page

  1. Ancestors and the lowest common ancestor
  2. LCA in a binary tree
  3. Traced: finding the LCA of 6 and 4
  4. LCA in a BST: let the order decide
  5. Rebuilding a tree from its traversals
  6. Save a tree as text and build it back
  7. Practice questions (7)
  8. Make it stick
  9. What's next

Ancestors and the lowest common ancestor

An ancestor of a node is any node on the path from the root down to it (its parent, its grandparent, and so on up to the root). LeetCode also counts the node itself. The lowest common ancestor, short name LCA, of two nodes p and q is the lowest node that has both of them somewhere below it (in its subtree, meaning itself and everything under it). Think of a family tree. The LCA of two cousins is the grandparent they share, not the great-grandparent above.

This lesson has two parts. First, we find the LCA in two ways: once for any binary tree, and once for a BST, where the order of the values makes it very easy. Second, we go the other way and build a tree from a list. The list can be two tree walks, or a saved string.

LCA in a binary tree

If the values have no order, you cannot know where p and q are. So search the whole tree with a recursive function (a function that calls itself on a smaller part of the problem) that answers one question: "what do you find in this part of the tree?" Each call returns:

  • null if neither target is in this part of the tree,
  • the target node, if it found exactly one (or if the node itself is a target),
  • the LCA, if it found both.

At a node, ask the left side and the right side. If both answers are not null, one target is on each side. So this node is where their paths split, and it is the LCA. If only one side answered, pass that answer up as it is. If the node itself is p or q, return it at once. The other target is either below it (then this node is the LCA) or somewhere else (then a higher node that finds both will notice).

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 gap  if (!arr.length || 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 (i < arr.length && 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 find(root, val) {               // helper for the demo: the node holding val  if (root === null) return null;  if (root.val === val) return root;  return find(root.left, val) || find(root.right, val);}function lowestCommonAncestor(root, p, q) {  if (root === null) return null;        // fell off the tree: nothing here  if (root === p || root === q) return root;   // found one of the two targets  const left = lowestCommonAncestor(root.left, p, q);  const right = lowestCommonAncestor(root.right, p, q);  if (left && right) return root;        // one target on each side: this is the meeting point  return left || right;                  // both on one side (or neither): pass that answer up}const root = buildTree([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);console.log(lowestCommonAncestor(root, find(root, 5), find(root, 1)).val); // 3console.log(lowestCommonAncestor(root, find(root, 6), find(root, 4)).val); // 5console.log(lowestCommonAncestor(root, find(root, 5), find(root, 4)).val); // 5  (a node may be its own ancestor)

Each node is visited once, so the time is O(n). The recursion goes as deep as the tree is tall, so the space is O(h). That is O(log n) for a balanced tree and O(n) for one long chain. The code assumes that both nodes are really in the tree, as the problem promises. Notice that we compare nodes (root === p), not values. This is safe only when we hold the real node objects.

Traced: finding the LCA of 6 and 4

Watch the calls list. It is the recursion stack: the chain of nodes that are waiting for their children to answer.

step 1 / 25
Set up
find the LCA of p = 6 and q = 4

The tree is [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]. To keep the trace short, we do not show the calls on missing (null) children. They just return null.

▶function lca(node, p, q) {2  if (node === null) return null;3  if (node === p || node === q) return node;4  const left = lca(node.left, p, q);5  const right = lca(node.right, p, q);6  if (left && right) return node;7  return left || right;8}
Variables
p6
q4
calls[]
Console
(nothing printed yet)
6 is on the left side of node 5 and 4 is on its right side. So node 5 is the first place to hear two different answers. Node 3 then hears from its left side, and its right side has nothing, so it just passes 5 up. · interactive

LCA in a BST: let the order decide

In a binary search tree (lesson 44), everything on the left side of a node is smaller than the node, and everything on the right side is bigger. So at any node you can tell where both targets are, without searching:

  • Both values are smaller than the node: the LCA is on the left side, so step left.
  • Both values are bigger: step right.
  • Otherwise the values split (one is smaller and one is bigger), or one of them equals the node. This node is the LCA.

This is a plain loop. It needs no recursion and no stack. It is one walk from the root down a single path.

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 gap  if (!arr.length || 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 (i < arr.length && 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 lcaBST(root, p, q) {  let cur = root;  while (cur !== null) {    if (p.val < cur.val && q.val < cur.val) cur = cur.left;        // both smaller: the LCA is on the left    else if (p.val > cur.val && q.val > cur.val) cur = cur.right;  // both bigger: the LCA is on the right    else return cur;                                               // they split here (or one equals cur)  }  return null;}const root = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);const node = (v) => { let c = root; while (c.val !== v) c = v < c.val ? c.left : c.right; return c; };console.log(lcaBST(root, node(2), node(8)).val); // 6console.log(lcaBST(root, node(2), node(4)).val); // 2console.log(lcaBST(root, node(3), node(5)).val); // 4

Time is O(h) and space is O(1). This is better than the general solution in both time and space. It is also why interviewers ask for both versions. They want to see: "Did you notice that the tree is a BST, and did you use that?"

Use the information you are given
If a problem says "binary search tree", the order of the values is a gift. Whenever a tree problem mentions a BST, ask what the order lets you skip.

Rebuilding a tree from its traversals

Lesson 41 gave you the three depth-first orders. Preorder visits the node, then its left side, then its right side. Inorder visits the left side, then the node, then the right side. Postorder visits the left side, then the right side, then the node. Can lists of values bring a tree back? One list alone is not enough. Preorder [1, 2] fits a tree where 2 is the left child of 1, and also a tree where 2 is the right child. But preorder plus inorder (when all values are different) gives exactly one tree:

  • Preorder is root, left, right. So its first value is the root.
  • Find that value in the inorder list. Inorder is left, root, right. So everything to its left is the left side, and everything to its right is the right side. This also tells you how many nodes the left side has.
  • Do the same for the two parts. Preorder visits the left side before the right side. So the next unused preorder value is the root of the left side. After the left side is finished, the next one is the root of the right side.

The slow way copies parts of the arrays with slice and searches for a value with indexOf on every call. In the worst case that costs O(n²). The fast way builds a Map (a lookup table) once, from each value to its position in the inorder list. It keeps one moving position in the preorder list. It describes each part of the tree by a range [lo, hi] in the inorder list, instead of copying.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}function toLevelArray(root) {            // level-order values with null gaps, trailing nulls trimmed  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {    const n = queue[i];    if (n === null) { out.push(null); continue; }    out.push(n.val);    queue.push(n.left, n.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function buildTree(preorder, inorder) {  const indexOf = new Map();                       // value -> its position in the inorder list  inorder.forEach((v, i) => indexOf.set(v, i));  let next = 0;                                    // which preorder value is the next root  function build(lo, hi) {                         // build the subtree for inorder[lo..hi]    if (lo > hi) return null;                      // empty range: no node    const val = preorder[next++];                  // preorder always starts with the root    const mid = indexOf.get(val);                  // everything left of mid is the left subtree    const node = new TreeNode(val);    node.left = build(lo, mid - 1);                // left first, because preorder is root, left, right    node.right = build(mid + 1, hi);    return node;  }  return build(0, inorder.length - 1);}console.log(toLevelArray(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]))); // [3, 9, 20, null, null, 15, 7]console.log(toLevelArray(buildTree([1, 2, 3], [3, 2, 1])));                // [1, 2, null, 3]
Dry run · preorder [3, 9, 20, 15, 7], inorder [9, 3, 15, 20, 7]
Call (inorder range)Next preorder valuePosition in inorderResult
build(0, 4)31root 3; the left side uses [0..0], the right side uses [2..4]
build(0, 0)90leaf 9 (both children get empty ranges)
build(2, 4)203node 20; the left side uses [2..2], the right side uses [4..4]
build(2, 2)152leaf 15
build(4, 4)74leaf 7

The preorder position moves through 3, 9, 20, 15, 7 in exactly the order of the calls. That is why one counter is enough.

Inorder plus postorder works the same way, with two changes. The root is the last postorder value. And postorder is left, right, root, so you read it from the end and build the right side first. Preorder plus postorder, without inorder, cannot always decide. A node with only one child could have it on either side.

Distinct values only
The Map trick needs every value to appear only once. With repeated values, the question "where is this value in the inorder list?" has more than one answer. Then the rebuilt tree is not unique. Interview questions promise that all values are different.

Save a tree as text and build it back

To serialize a tree means to turn it into a string of text that you can save or send. To deserialize means to build the tree back from that text. We saw above that one list is not enough. But if you also write down where the children are missing, one walk is enough. Write a marker (here #) for every missing child. You can read a preorder with markers back with the same recursion that wrote it. Read one piece of text (a token). If it is #, return null. Otherwise make a node. Let the next tokens fill its left side, and then its right side.

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 gap  if (!arr.length || 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 (i < arr.length && 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 serialize(root) {  const out = [];  (function go(node) {    if (node === null) { out.push("#"); return; }   // a marker for a missing child    out.push(node.val);    go(node.left);    go(node.right);  })(root);  return out.join(",");}function deserialize(text) {  const tokens = text.split(",");  let i = 0;  function go() {    const token = tokens[i++];    if (token === "#") return null;    const node = new TreeNode(Number(token));    node.left = go();                               // the tokens come back in the same order they left    node.right = go();    return node;  }  return go();}const root = buildTree([1, 2, 3, null, null, 4, 5]);const text = serialize(root);console.log(text);                                  // 1,2,#,#,3,4,#,#,5,#,#console.log(serialize(deserialize(text)) === text); // trueconsole.log(serialize(null));                       // #

The text for the tree above is 1,2,#,#,3,4,#,#,5,#,#. A tree with n nodes has n + 1 missing children. So the string has 2n + 1 tokens, and both directions take O(n).

The other popular format is level order (row by row), the same one LeetCode prints. It uses a queue (a first-in, first-out line). When saving, we push both children, including nulls, so every gap gets a marker. When reading back, we keep a queue of parents that wait for children, and we give each parent two tokens.

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 gap  if (!arr.length || 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 (i < arr.length && 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 serializeLevel(root) {  if (root === null) return "";  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {          // walking an index instead of shift() keeps this O(n)    const node = queue[i];    if (node === null) { out.push("#"); continue; }    out.push(node.val);    queue.push(node.left, node.right);              // null children are queued too, so they get a marker  }  return out.join(",");}function deserializeLevel(text) {  if (text === "") return null;  const tokens = text.split(",");  const root = new TreeNode(Number(tokens[0]));  const queue = [root];  let t = 1;                                        // next token to read  for (let i = 0; i < queue.length; i++) {    const node = queue[i];    if (tokens[t] !== undefined && tokens[t] !== "#") { node.left = new TreeNode(Number(tokens[t])); queue.push(node.left); }    t++;    if (tokens[t] !== undefined && tokens[t] !== "#") { node.right = new TreeNode(Number(tokens[t])); queue.push(node.right); }    t++;  }  return root;}const text = serializeLevel(buildTree([1, 2, 3, null, null, 4, 5]));console.log(text);                                           // 1,2,3,#,#,4,5,#,#,#,#console.log(serializeLevel(deserializeLevel(text)) === text); // true

This version writes some extra markers at the end (the four #). They do no harm. In an interview, choose the preorder version unless you are asked for another. It is shorter and needs no queue.

Remember the separator and the empty tree
Use a separator (here a comma), so that 12 and 1,2 cannot be mixed up. Also test the empty tree and negative numbers. Never assume that a value is a single digit.

Practice questions

For each question, first ask what a recursive call should return (a node, a count, or a true/false flag). Then ask what it needs to be told (a range, or the largest value so far).

Q1Lowest common ancestor of a binary treeMedium

You get a binary tree and two nodes p and q that are both in it. Return their lowest common ancestor: the lowest node that has both of them below it (a node counts as being below itself).

Example 1
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
Explanation: 5 is on the left side of 3 and 1 is on the right side, so the paths split at the root.
Example 2
Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Explanation: 4 is below 5, and a node counts as its own ancestor.
Stuck? Open one hint at a time
Hint 1
Think about the path from the root to p and the path from the root to q. At which node do the two paths stop being the same?
Hint 2
Or let each recursive call report what it finds in its part of the tree: nothing, one target, or the answer.
Hint 3
If both the left call and the right call return something, the current node is the meeting point.
Show all 2 solutions with explanations
Approach 1Compare the two root paths
The idea
  1. Find the path from the root to p and the path from the root to q (each is a list of nodes).
  2. Walk both lists together. The last node where they are still the same is the LCA.
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 gap  if (!arr.length || 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 (i < arr.length && 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 find(root, val) {               // demo helper: the node holding val  if (root === null) return null;  if (root.val === val) return root;  return find(root.left, val) || find(root.right, val);}function pathTo(root, target, path = []) {  if (root === null) return null;  path.push(root);  if (root === target) return path;  const found = pathTo(root.left, target, path) || pathTo(root.right, target, path);  if (found) return found;  path.pop();                              // dead end: undo and let the caller try elsewhere  return null;}function lowestCommonAncestor(root, p, q) {  const a = pathTo(root, p), b = pathTo(root, q);  let lca = null;  for (let i = 0; i < a.length && i < b.length && a[i] === b[i]; i++) lca = a[i];  return lca;}const root = buildTree([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);console.log(lowestCommonAncestor(root, find(root, 5), find(root, 1)).val); // 3console.log(lowestCommonAncestor(root, find(root, 5), find(root, 4)).val); // 5
How it works

Two searches and one comparison: O(n) time, O(h) space for the paths. It is correct and easy to explain, but it needs two passes and extra lists.

Approach 2One recursive pass
The idea
  1. If the node is null, p or q, return it.
  2. Ask the left side and the right side.
  3. If both answered, return this node. Otherwise return the one that answered (or null).
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 gap  if (!arr.length || 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 (i < arr.length && 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 find(root, val) {               // demo helper: the node holding val  if (root === null) return null;  if (root.val === val) return root;  return find(root.left, val) || find(root.right, val);}function lowestCommonAncestor(root, p, q) {  if (root === null || 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;  return left || right;}const root = buildTree([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);console.log(lowestCommonAncestor(root, find(root, 5), find(root, 1)).val); // 3console.log(lowestCommonAncestor(root, find(root, 5), find(root, 4)).val); // 5console.log(lowestCommonAncestor(root, find(root, 7), find(root, 8)).val); // 3
How it works

It is safe to return at p or q without looking below. If the other target is under it, this node is the LCA. If not, a higher node will find the other target on its other side. O(n) time, O(h) space.

Which approach should you use?

Use the one-pass recursion. You can mention the path comparison first, as an easy starting point that is simple to check. (LeetCode 236.)

Q2Lowest common ancestor of a BSTMedium

The same question, but now the tree is a binary search tree and all values are different. Return the LCA of p and q.

Example 1
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
Explanation: 2 is smaller than 6 and 8 is bigger, so they split at the root.
Example 2
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Explanation: 4 is on the right side of 2, and a node counts as its own ancestor.
Stuck? Open one hint at a time
Hint 1
At any node, compare both values with the value of the node. When are both on the same side?
Hint 2
While both are on the same side, you can step that way and never look at the other side.
Show all 3 solutions with explanations
Approach 1Ignore the order of the values
The idea

Use the general binary-tree recursion from question 1. It works on any tree, including a BST, but it can visit every node.

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 gap  if (!arr.length || 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 (i < arr.length && 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 lowestCommonAncestor(root, p, q) {  if (root === null || 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;  return left || right;}const root = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);const node = (v) => { let c = root; while (c.val !== v) c = v < c.val ? c.left : c.right; return c; };console.log(lowestCommonAncestor(root, node(2), node(8)).val); // 6console.log(lowestCommonAncestor(root, node(3), node(5)).val); // 4
How it works

O(n) time, O(h) space. Correct, but it does not use the key fact that the values in the tree are ordered.

Approach 2Walk down using the order (a loop)
The idea

Start at the root. If both values are smaller, go left. If both are bigger, go right. Otherwise stop. This node is the LCA.

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 gap  if (!arr.length || 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 (i < arr.length && 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 lowestCommonAncestor(root, p, q) {  let cur = root;  while (cur !== null) {    if (p.val < cur.val && q.val < cur.val) cur = cur.left;    else if (p.val > cur.val && q.val > cur.val) cur = cur.right;    else return cur;  }  return null;}const root = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);const node = (v) => { let c = root; while (c.val !== v) c = v < c.val ? c.left : c.right; return c; };console.log(lowestCommonAncestor(root, node(2), node(8)).val); // 6console.log(lowestCommonAncestor(root, node(2), node(4)).val); // 2console.log(lowestCommonAncestor(root, node(3), node(5)).val); // 4
How it works

O(h) time and O(1) space. The stop case covers three situations at once: the values split, p equals the node, or q equals the node.

Approach 3Walk down using the order (recursion)
The idea

The same choice written as a recursion. Some people find it easier to read.

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 gap  if (!arr.length || 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 (i < arr.length && 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 lowestCommonAncestor(root, p, q) {  if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);  if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);  return root;}const root = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);const node = (v) => { let c = root; while (c.val !== v) c = v < c.val ? c.left : c.right; return c; };console.log(lowestCommonAncestor(root, node(0), node(5)).val); // 2console.log(lowestCommonAncestor(root, node(7), node(9)).val); // 8
How it works

The same O(h) time, but O(h) stack space for the calls. The loop is better when the tree is deep.

Which approach should you use?

Use the loop. It is fast and needs no extra memory. (LeetCode 235.)

Q3Construct a tree from preorder and inorder traversalsMedium

You get the preorder and inorder lists of a binary tree whose values are all different. Rebuild the tree and return its root. The examples show the tree in level order (row by row).

Example 1
Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
Explanation: 3 is first in preorder, so it is the root. In inorder, 9 is to the left of 3, and 15, 20, 7 are to the right of it.
Example 2
Input: preorder = [1, 2], inorder = [2, 1]
Output: [1, 2]
Explanation: The root is 1. In the inorder list, 2 is to the left of 1, so it is the left child.
Stuck? Open one hint at a time
Hint 1
In a preorder list, which value is always the root of the whole tree?
Hint 2
Find that root in the inorder list. How many values are to its left? What does that tell you about the left side of the tree?
Hint 3
Searching the inorder list each time is slow. Can you look up the position in O(1)?
Show all 2 solutions with explanations
Approach 1Slice and search
The idea
  1. The root is preorder[0]; find it in inorder with indexOf.
  2. Cut both arrays into a left part and a right part, and call the function on each part.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}function toLevelArray(root) {            // level-order values, null gaps, trailing nulls trimmed  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {    const n = queue[i];    if (n === null) { out.push(null); continue; }    out.push(n.val);    queue.push(n.left, n.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function buildTree(preorder, inorder) {  if (preorder.length === 0) return null;  const root = new TreeNode(preorder[0]);  const mid = inorder.indexOf(preorder[0]);          // number of nodes in the left subtree  root.left = buildTree(preorder.slice(1, 1 + mid), inorder.slice(0, mid));  root.right = buildTree(preorder.slice(1 + mid), inorder.slice(mid + 1));  return root;}console.log(toLevelArray(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]))); // [3, 9, 20, null, null, 15, 7]console.log(toLevelArray(buildTree([1, 2], [2, 1])));                      // [1, 2]
How it works

Each call copies arrays and scans for the root. A tree shaped like a chain costs O(n²) time and space. It is the clearest way to see the idea.

Approach 2Index map and a moving position
The idea
  1. Build a Map (a lookup table) from each value to its inorder position, once.
  2. Keep one position in the preorder list. Each call takes the next preorder value as its root. It then splits the inorder range at the position from the Map.
  3. Build the left side first, then the right side.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}function toLevelArray(root) {            // level-order values, null gaps, trailing nulls trimmed  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {    const n = queue[i];    if (n === null) { out.push(null); continue; }    out.push(n.val);    queue.push(n.left, n.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function buildTree(preorder, inorder) {  const indexOf = new Map();  inorder.forEach((v, i) => indexOf.set(v, i));  let next = 0;  function build(lo, hi) {    if (lo > hi) return null;    const val = preorder[next++];    const mid = indexOf.get(val);    const node = new TreeNode(val);    node.left = build(lo, mid - 1);    node.right = build(mid + 1, hi);    return node;  }  return build(0, inorder.length - 1);}console.log(toLevelArray(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]))); // [3, 9, 20, null, null, 15, 7]console.log(toLevelArray(buildTree([1, 2], [2, 1])));                      // [1, 2]console.log(toLevelArray(buildTree([-1], [-1])));                          // [-1]
How it works

O(n) time and O(n) space (the Map plus the recursion). The order of the two recursive calls matters. The left call must go first, because the preorder position reaches the values of the left side before the values of the right side.

Which approach should you use?

Use the Map with a moving position. Show the slice version first only to explain the idea. (LeetCode 105.)

Q4Construct a tree from inorder and postorder traversalsMedium

You get the inorder and postorder lists of a binary tree whose values are all different. Rebuild the tree.

Example 1
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: [3, 9, 20, null, null, 15, 7]
Explanation: The last postorder value, 3, is the root. In inorder, 9 is to the left of it and the rest are to the right.
Example 2
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Explanation: There is a single node.
Stuck? Open one hint at a time
Hint 1
This is the previous problem turned around. In a postorder list, where is the root?
Hint 2
Postorder is left, right, root. If you read it from the end, which side do you meet first?
Show all 2 solutions with explanations
Approach 1Slice and search
The idea

The root is the last postorder value. Find it in the inorder list. The left part has mid nodes, and this also tells you where to cut the postorder list.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}function toLevelArray(root) {            // level-order values, null gaps, trailing nulls trimmed  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {    const n = queue[i];    if (n === null) { out.push(null); continue; }    out.push(n.val);    queue.push(n.left, n.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function buildTree(inorder, postorder) {  if (postorder.length === 0) return null;  const val = postorder[postorder.length - 1];  const mid = inorder.indexOf(val);  const root = new TreeNode(val);  root.left = buildTree(inorder.slice(0, mid), postorder.slice(0, mid));  root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid, postorder.length - 1));  return root;}console.log(toLevelArray(buildTree([9, 3, 15, 20, 7], [9, 15, 7, 20, 3]))); // [3, 9, 20, null, null, 15, 7]console.log(toLevelArray(buildTree([-1], [-1])));                          // [-1]
How it works

O(n²), because of the copying and searching.

Approach 2Index map, reading postorder from the end
The idea

Move a position backwards, starting at the last postorder value. Postorder ends with the right side, so build the right side first, then the left side.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}function toLevelArray(root) {            // level-order values, null gaps, trailing nulls trimmed  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {    const n = queue[i];    if (n === null) { out.push(null); continue; }    out.push(n.val);    queue.push(n.left, n.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function buildTree(inorder, postorder) {  const indexOf = new Map();  inorder.forEach((v, i) => indexOf.set(v, i));  let next = postorder.length - 1;  function build(lo, hi) {    if (lo > hi) return null;    const val = postorder[next--];    const mid = indexOf.get(val);    const node = new TreeNode(val);    node.right = build(mid + 1, hi);       // right first: it sits just before the root in postorder    node.left = build(lo, mid - 1);    return node;  }  return build(0, inorder.length - 1);}console.log(toLevelArray(buildTree([9, 3, 15, 20, 7], [9, 15, 7, 20, 3]))); // [3, 9, 20, null, null, 15, 7]console.log(toLevelArray(buildTree([2, 1], [2, 1])));                      // [1, 2]
How it works

O(n) time and space. If you build the left side first here, the left side takes the values of the right side. This is a classic bug.

Which approach should you use?

Use the Map version, and build the right side first. (LeetCode 106.)

Q5Serialize and deserialize a binary treeHard

Write serialize(root), which turns a binary tree into a string of text, and deserialize(data), which builds the same tree back from that string. Any format works, as long as you get exactly the same tree back.

Example 1
Input: root = [1, 2, 3, null, null, 4, 5]
Output: "1,2,#,#,3,4,#,#,5,#,#"
Explanation: This is preorder, with # standing for a missing child. Reading it back gives the same tree.
Example 2
Input: root = []
Output: "#"
Explanation: The empty tree is just one missing child.
Stuck? Open one hint at a time
Hint 1
Inorder alone can fit more than one tree. What extra information would fix that?
Hint 2
Write a marker for every null child. Then a plain preorder is enough.
Hint 3
To read it back, use the same recursion and take the tokens (the pieces of text) one by one, in order.
Show all 2 solutions with explanations
Approach 1Preorder with null markers
The idea
  1. Save as text: visit root, left, right. Write the value, or # for null.
  2. Read back: read a token. If it is #, the result is null. Otherwise make a node, and build its left side and then its right side from the next tokens.
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 gap  if (!arr.length || 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 (i < arr.length && 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 serialize(root) {  const out = [];  (function go(node) {    if (node === null) { out.push("#"); return; }    out.push(node.val);    go(node.left);    go(node.right);  })(root);  return out.join(",");}function deserialize(data) {  const tokens = data.split(",");  let i = 0;  function go() {    const token = tokens[i++];    if (token === "#") return null;    const node = new TreeNode(Number(token));    node.left = go();    node.right = go();    return node;  }  return go();}const data = serialize(buildTree([1, 2, 3, null, null, 4, 5]));console.log(data);                                  // 1,2,#,#,3,4,#,#,5,#,#console.log(serialize(deserialize(data)) === data); // trueconsole.log(serialize(buildTree([-7, null, 12])));  // -7,#,12,#,#
How it works

O(n) time and space. The comma matters, because it keeps -7 and 12 as whole numbers. Number(token) handles negative numbers.

Approach 2Level order with null markers
The idea

To save, use a queue and push both children, even null ones. To read back, use a queue of nodes that wait for their children. Each node takes the next two tokens.

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 gap  if (!arr.length || 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 (i < arr.length && 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 serialize(root) {  if (root === null) return "";  const out = [], queue = [root];  for (let i = 0; i < queue.length; i++) {    const node = queue[i];    if (node === null) { out.push("#"); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  return out.join(",");}function deserialize(data) {  if (data === "") return null;  const tokens = data.split(",");  const root = new TreeNode(Number(tokens[0]));  const queue = [root];  let t = 1;  for (let i = 0; i < queue.length; i++) {    const node = queue[i];    if (tokens[t] !== undefined && tokens[t] !== "#") { node.left = new TreeNode(Number(tokens[t])); queue.push(node.left); }    t++;    if (tokens[t] !== undefined && tokens[t] !== "#") { node.right = new TreeNode(Number(tokens[t])); queue.push(node.right); }    t++;  }  return root;}const data = serialize(buildTree([1, 2, 3, null, null, 4, 5]));console.log(data);                                  // 1,2,3,#,#,4,5,#,#,#,#console.log(serialize(deserialize(data)) === data); // trueconsole.log(serialize(deserialize("")));            // (empty string)
How it works

O(n) time and space. It matches the format LeetCode shows, but it has more steps to keep track of than the recursive version.

Which approach should you use?

Use preorder with markers. It is the shortest and the easiest to get right. (LeetCode 297.)

Q6Count good nodes in a binary treeMedium

A node X is good if no node on the path from the root to X has a value greater than X. Return how many good nodes there are.

Example 1
Input: root = [3, 1, 4, 3, null, 1, 5]
Output: 4
Explanation: The good nodes are the root 3, the 4, the left-left 3 and the 5. Each 1 has a bigger node above it.
Example 2
Input: root = [3, 3, null, 4, 2]
Output: 3
Explanation: The root 3, the 3 and the 4 are good. The 2 has a 3 above it, which is bigger.
Stuck? Open one hint at a time
Hint 1
A node is good if no node on its path from the root is bigger. Which single number describes the path so far?
Hint 2
Pass the largest value seen so far down as an argument.
Show all 2 solutions with explanations
Approach 1Check the whole path for every node
The idea

Keep the real path in a list. At each node, check that every value on the path is at most the value of this node.

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 gap  if (!arr.length || 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 (i < arr.length && 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 goodNodes(root) {  let count = 0;  const path = [];  function dfs(node) {    if (node === null) return;    if (path.every((v) => v <= node.val)) count++;    path.push(node.val);    dfs(node.left);    dfs(node.right);    path.pop();  }  dfs(root);  return count;}console.log(goodNodes(buildTree([3, 1, 4, 3, null, 1, 5]))); // 4console.log(goodNodes(buildTree([3, 3, null, 4, 2])));       // 3
How it works

O(n·h). Each node scans its path, which is O(n²) on a tree shaped like a chain.

Approach 2DFS carrying the maximum
The idea

Pass maxSoFar down. A node is good when its value is at least maxSoFar. Its children get the larger of the two numbers.

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 gap  if (!arr.length || 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 (i < arr.length && 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 goodNodes(root) {  function dfs(node, maxSoFar) {    if (node === null) return 0;    const good = node.val >= maxSoFar ? 1 : 0;    const bigger = Math.max(maxSoFar, node.val);    return good + dfs(node.left, bigger) + dfs(node.right, bigger);  }  return dfs(root, -Infinity);}console.log(goodNodes(buildTree([3, 1, 4, 3, null, 1, 5]))); // 4console.log(goodNodes(buildTree([3, 3, null, 4, 2])));       // 3console.log(goodNodes(buildTree([1])));                      // 1
How it works

O(n) time and O(h) space. We start with -Infinity (smaller than any number), so the root is always good, even if its value is negative.

Which approach should you use?

Carry the maximum down. One number replaces the whole path. (LeetCode 1448.)

Q7Count complete tree nodesEasy

You get the root of a complete binary tree. Return the number of nodes, and try to be faster than O(n).

Example 1
Input: root = [1, 2, 3, 4, 5, 6]
Output: 6
Explanation: All levels are full except the last one, which is filled from the left.
Example 2
Input: root = []
Output: 0
Explanation: There are no nodes.
Stuck? Open one hint at a time
Hint 1
Counting every node works. But the tree is complete: all levels are full except maybe the last one, which fills from the left. Can that help?
Hint 2
Compare the depth along the leftmost edge with the depth along the rightmost edge. If they are equal, the whole tree is perfect (every level full), and you can work out its size with a formula.
Hint 3
If they are different, count the root plus the two sides, with recursion. One of the two sides will be perfect.
Show all 2 solutions with explanations
Approach 1Visit every node
The idea

Count with plain recursion: 1 + count(left) + count(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 gap  if (!arr.length || 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 (i < arr.length && 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 countNodes(root) {  if (root === null) return 0;  return 1 + countNodes(root.left) + countNodes(root.right);}console.log(countNodes(buildTree([1, 2, 3, 4, 5, 6]))); // 6console.log(countNodes(null));                          // 0
How it works

O(n). Correct for any tree, but it does not use the fact that the tree is complete.

Approach 2Perfect parts counted by a formula
The idea
  1. Measure the height by going only left from the root, and again by going only right.
  2. If both heights are equal, the tree is perfect and has 2^height − 1 nodes.
  3. Otherwise return 1 + the count of the left side + the count of the right side.
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 gap  if (!arr.length || 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 (i < arr.length && 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 countNodes(root) {  if (root === null) return 0;  let leftHeight = 0, rightHeight = 0;  for (let n = root; n !== null; n = n.left) leftHeight++;  for (let n = root; n !== null; n = n.right) rightHeight++;  if (leftHeight === rightHeight) return 2 ** leftHeight - 1;    // a perfect tree: no need to look inside  return 1 + countNodes(root.left) + countNodes(root.right);}console.log(countNodes(buildTree([1, 2, 3, 4, 5, 6])));       // 6console.log(countNodes(buildTree([1, 2, 3, 4, 5, 6, 7])));    // 7console.log(countNodes(buildTree([1, 2, 3, 4, 5, 6, 7, 8]))); // 8
How it works

At each level, at least one of the two recursive calls meets a perfect part and returns after a height check of O(log n). There are about log n levels, and each costs O(log n). So the time is O(log² n) and the space is O(log n). If the left and right heights match, the last level is full. In a complete tree, that means every level is full.

Which approach should you use?

Use the height trick if you notice the word "complete". The plain count is the safe fallback. (LeetCode 222.)

Make it stick

Make it stick — close this page, then
  1. Explain what each recursive call returns in the binary-tree LCA, and the one condition that makes a node the answer.
  2. Say how the BST LCA uses the order of the values, and why it needs only O(1) extra space.
  3. Explain how preorder plus inorder gives exactly one tree, and why a Map from value to inorder position gives O(n).
  4. Explain why preorder alone cannot rebuild a tree, but preorder with null markers can.

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

That finishes the tree part of the series. Lesson 46 starts Part 12 with the heap. A heap is a tree stored inside a plain array, and it always keeps its smallest (or largest) item on top. It is the tool for "the k largest" questions, and for taking the best item again and again from what is left.

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

Related series