DSA for Interviews, From Zero

Part 11 · Lesson 41 · read

Binary Trees and Traversals

Root, leaves and height. Preorder, inorder and postorder, drawn and coded.

On this page

  1. Why trees?
  2. Tree vocabulary
  3. A node in JavaScript
  4. Building a tree from an array
  5. Three ways to walk a tree
  6. Traced: one walk, three orders
  7. Walking with an explicit stack
  8. Depth, same tree, invert
  9. Practice questions (7)
  10. Make it stick
  11. What's next

Why trees?

So far every structure was a straight line: an array, a string, a linked list, a stack. A line is the wrong shape for things that branch. Think of a folder with sub-folders, a family tree, the nested tags of a web page, or the choices in a game. A tree is a group of nodes (boxes that hold a value). Each node can lead to several other nodes below it, and there are no loops. In this lesson we meet the most common kind, the binary tree. In a binary tree every node has at most two children, called the left child and the right child.

The big new idea: a tree is recursive. Recursive means made of smaller copies of itself, like a set of nesting dolls. In code, recursion is a function that calls itself on a smaller part of the problem. Look at any node and everything below it, and you see a smaller tree. So you can answer a question about a whole tree by answering the same question for the left part and the right part, then joining the two answers. Almost every tree problem in this part of the series uses this one trick.

Tree vocabulary

We use this example tree for the whole lesson. Keep the picture in mind while you read the table.

      1
     / \
    2   3
   / \
  4   5
Dry run · the words, on the tree above
WordIn this treeMeaning
root1the one node at the top; it is the only node with no parent
parent / child2 is the parent of 4 and 5a parent is the node right above its children; each node has at most one parent
leaf4, 5 and 3a node with no children
edge1-2, 1-3, 2-4, 2-5a link between a parent and a child
subtree2, 4, 5a node together with everything below it; the subtree of 2 is a small tree on its own
depth of a nodedepth(4) = 2how many edges (links) you cross going from the root down to that node (the root has depth 0)
height of a tree2the number of edges on the longest path from the root down to a leaf

Careful: some books count height and depth in nodes, not edges. LeetCode's 'maximum depth' counts nodes, so this tree has maximum depth 3. Always check which one the problem means.

A node in JavaScript

A node is a small object with a value and two links. A link is either another node or null, which means "nothing here". A whole tree is just its root node. From the root you can reach every other node by following links, just like a linked list is just its head.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;      // the value stored in this node    this.left = left;    // another TreeNode, or null if there is no left child    this.right = right;  // another TreeNode, or null if there is no right child  }}//      1//     / \//    2   3//   / \//  4   5const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));console.log(root.left.right.val); // 5console.log(root.right.left);     // null  (3 is a leaf, it has no children)
null is a tree too
An empty tree is written as null. Almost every recursive tree function starts with if (node === null) return .... That line is the base case. The base case is the smallest problem, the one you can answer right away without calling the function again.

Building a tree from an array

Linking nodes by hand takes a long time. LeetCode shows trees as arrays like [3, 9, 20, null, null, 15, 7]. This is the level-order form. You read the tree row by row, from the top, left to right. You write null where a child is missing. Here 3 is the root and its children are 9 and 20. Node 9 has no children (two nulls). Node 20 has children 15 and 7.

To build the tree, keep a queue of nodes that still need children. A queue is a first-in, first-out line, like people waiting at a shop (see lesson 39). Take the next waiting node. Give it the next two array values as its left and right child. We use a head number instead of shift(), because removing from the front of a JavaScript array is slow. We will reuse this helper in most of the samples to come.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}// Level-order array -> tree. null marks a missing child (the format LeetCode uses).function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];          // nodes that still need their children attached  let head = 0;                  // read position in the queue (no slow shift)  let i = 1;                     // next unread value in arr  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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;}const root = buildTree([3, 9, 20, null, null, 15, 7]);console.log(root.val, root.left.val, root.right.val);       // 3 9 20console.log(root.right.left.val, root.right.right.val);     // 15 7console.log(root.left.left, root.left.right);               // null null

Three ways to walk a tree

To traverse a tree means to visit every node exactly once. A line has one natural order. A tree gives you a choice. The three classic depth-first orders differ in only one thing: when you write down the current node, compared with its two sides:

  • Preorder: node, then left subtree, then right subtree. ("pre" = before the children.)
  • Inorder: left subtree, then node, then right subtree. ("in" = between the children.)
  • Postorder: left subtree, then right subtree, then node. ("post" = after the children.)

Depth-first means we go all the way down one branch before we come back to try another branch. Each order uses the same three lines, just in a different order:

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 preorder(node, out = []) {  if (node === null) return out;  out.push(node.val);          // visit first ...  preorder(node.left, out);  preorder(node.right, out);  return out;}function inorder(node, out = []) {  if (node === null) return out;  inorder(node.left, out);  out.push(node.val);          // ... visit in the middle ...  inorder(node.right, out);  return out;}function postorder(node, out = []) {  if (node === null) return out;  postorder(node.left, out);  postorder(node.right, out);  out.push(node.val);          // ... or visit last  return out;}const root = buildTree([1, 2, 3, 4, 5]);console.log(preorder(root));  // [1, 2, 4, 5, 3]console.log(inorder(root));   // [4, 2, 5, 1, 3]console.log(postorder(root)); // [4, 5, 2, 3, 1]

Recursion keeps track of where to go back to without extra work from you. The language keeps a call stack, a pile of open function calls that remembers where to return. Time is O(n), because each node is visited once. Extra space is O(h) for the call stack, where h is the height of the tree. For a well-balanced tree (both sides about equal) h is about log n. For a tree that is one long chain, h can be as big as n.

Traced: one walk, three orders

One walk can build all three orders at once. We pass every node three times: on the way down, after coming back from the left side, and after coming back from the right side. Watch the three result lists grow at different times.

step 1 / 17
Set up
walk(root)

We call walk on the root, node 1. Each call handles one node, then makes two more calls: one for the left side and one for the right side. The path shows the calls that are still open right now.

1function walk(node) {2  if (node === null) return;3  pre.push(node.val);4  walk(node.left);5  ino.push(node.val);6  walk(node.right);7  post.push(node.val);8}▶walk(root);
Variables
pre[]
ino[]
post[]
Console
(nothing printed yet)
The same trip around the tree, written down at three different moments. Preorder gives 1 2 4 5 3, inorder gives 4 2 5 1 3, postorder gives 4 5 2 3 1. · interactive

Walking with an explicit stack

Recursion can fail on a very deep tree. A chain of 100,000 nodes overflows the call stack (the call stack runs out of room). Interviewers also like to ask "now do it without recursion". The answer is to do the job the language did for you. Keep your own stack, which is a pile where you add and remove only at the top.

Preorder is the easiest. Pop a node, visit it, then push its children. A stack gives back the last item first. So push the right child before the left child, and the left child comes out first.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function preorderIterative(root) {  if (root === null) return [];  const out = [];  const stack = [root];  while (stack.length > 0) {    const node = stack.pop();    out.push(node.val);    if (node.right) stack.push(node.right);   // pushed first, so it comes out second    if (node.left) stack.push(node.left);     // pushed last, so it comes out next  }  return out;}const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));console.log(preorderIterative(root)); // [1, 2, 4, 5, 3]
Dry run · iterative preorder
StepStack (top on the right)Output so far
start[1][]
pop 1, visit, push 3 then 2[3, 2][1]
pop 2, visit, push 5 then 4[3, 5, 4][1, 2]
pop 4, visit (leaf)[3, 5][1, 2, 4]
pop 5, visit (leaf)[3][1, 2, 4, 5]
pop 3, visit (leaf)[][1, 2, 4, 5, 3]

Inorder needs one more idea. Before you visit a node, you must finish its whole left side. So go left as far as you can and push each node you pass. The stack remembers the way back. Then pop the leftmost node and visit it. After that, do the same for its right side.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function inorderIterative(root) {  const out = [];  const stack = [];  let cur = root;  while (cur !== null || stack.length > 0) {    while (cur !== null) {        // dive as far left as possible, remembering the way back      stack.push(cur);      cur = cur.left;    }    cur = stack.pop();            // the leftmost unvisited node    out.push(cur.val);    cur = cur.right;              // then do the same for its right subtree  }  return out;}const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));console.log(inorderIterative(root)); // [4, 2, 5, 1, 3]

Postorder is the hard one, because you visit a node only after both of its children. Here is a trick. Postorder (left, right, node) is exactly the reverse of (node, right, left). And (node, right, left) is just preorder with the children pushed in the opposite order. So run that, then reverse the result.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}// Postorder (left, right, node) is the reverse of "node, right, left".function postorderIterative(root) {  if (root === null) return [];  const out = [];  const stack = [root];  while (stack.length > 0) {    const node = stack.pop();    out.push(node.val);                       // node, then right, then left ...    if (node.left) stack.push(node.left);    if (node.right) stack.push(node.right);  }  return out.reverse();                       // ... reversed is left, right, node}const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));console.log(postorderIterative(root)); // [4, 5, 2, 3, 1]

All three take O(n) time and O(h) extra space for the stack, the same as the recursive versions. The difference is the limit on depth. Now it is your computer's memory, not the small call stack.

Depth, same tree, invert

Here is the recursive way of thinking on three classic questions. Each one follows the same recipe. First handle null. Then ask the question of the left and right sides. Then combine the two answers.

  • Maximum depth: an empty tree has depth 0. Otherwise the depth is 1 (for this node) plus the larger depth of the two sides.
  • Same tree: two empty trees match. One empty tree and one non-empty tree do not match. Otherwise the two values must match, and both pairs of sides must match too.
  • Invert: swap the left and right child of every node. Invert the children first, then swap them.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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;}// Number of nodes on the longest path from the root down to a leaf.function maxDepth(node) {  if (node === null) return 0;  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));}// Two trees are the same if their shapes match and every pair of values matches.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);}// Swap the two children of every node.function invertTree(node) {  if (node === null) return null;  const left = invertTree(node.left);  const right = invertTree(node.right);  node.left = right;  node.right = left;  return node;}function preorder(node, out = []) {  if (node === null) return out;  out.push(node.val);  preorder(node.left, out);  preorder(node.right, out);  return out;}console.log(maxDepth(buildTree([3, 9, 20, null, null, 15, 7])));                       // 3console.log(isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 3])));                  // trueconsole.log(isSameTree(buildTree([1, 2]), buildTree([1, null, 2])));                  // falseconsole.log(preorder(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9]))));                  // [4, 7, 9, 6, 2, 3, 1]
Check null before you touch .val
The most common tree bug is reading node.left.val when node.left is null. That gives the error "Cannot read properties of null". Put the null check at the top of the function. Then the rest of the function can be sure it has a real node.

Practice questions

For each question, decide two things first. Which moment do I need: before, between or after the children? And what does the base case return?

Q1Binary tree preorder traversalEasy

Return the preorder traversal (the list of node values in preorder) of a binary tree.

Example 1
Input: root = [1, null, 2, 3]
Output: [1, 2, 3]
Explanation: Visit 1, then its left side (nothing), then its right side. The right side is node 2, and its left child 3 comes next.
Example 2
Input: root = [1, 2, 3, 4, 5]
Output: [1, 2, 4, 5, 3]
Explanation: Node first, then the whole left side (2, 4, 5), then the right side (3).
Example 3
Input: root = []
Output: []
Explanation: An empty tree has nothing to visit.
Stuck? Open one hint at a time
Hint 1
Preorder means "node, left side, right side". Write the node down before the recursive calls (the calls to the same function).
Hint 2
Without recursion, use a stack (a pile where you add and remove only at the top). Which child must you push first, so that the other one comes out first?
Show all 2 solutions with explanations
Approach 1Recursion
The idea

If the node is null, stop. Otherwise add its value to the answer, then walk the left side, then the right side.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 preorderTraversal(root) {  const out = [];  function walk(node) {    if (node === null) return;    out.push(node.val);    walk(node.left);    walk(node.right);  }  walk(root);  return out;}console.log(preorderTraversal(buildTree([1, null, 2, 3])));  // [1, 2, 3]console.log(preorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [1, 2, 4, 5, 3]console.log(preorderTraversal(buildTree([])));              // []
How it works

O(n) time. O(h) space for the call stack (the pile of open calls), where h is the height of the tree. h can be as big as n for a tree that is one long chain.

Approach 2Explicit stack
The idea
  1. Start with the root on a stack.
  2. Pop a node, record it, then push its right child and then its left child.
  3. The left child is on top, so it is handled next. The whole left side is finished before we touch the right side.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 preorderTraversal(root) {  if (root === null) return [];  const out = [];  const stack = [root];  while (stack.length > 0) {    const node = stack.pop();    out.push(node.val);    if (node.right) stack.push(node.right);    if (node.left) stack.push(node.left);  }  return out;}console.log(preorderTraversal(buildTree([1, null, 2, 3])));  // [1, 2, 3]console.log(preorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [1, 2, 4, 5, 3]
How it works

O(n) time. Each level of the tree leaves at most one waiting sibling (the other child of the same parent) on the stack. So the stack holds at most about h + 1 nodes, which is O(h) space. There is no limit on recursion depth to worry about.

Which approach should you use?

Write the recursive one first. It is only three lines. If the interviewer says "without recursion", switch to the stack. (LeetCode 144.)

Q2Binary tree inorder traversalEasy

Return the inorder traversal (the list of node values in inorder) of a binary tree.

Example 1
Input: root = [1, null, 2, 3]
Output: [1, 3, 2]
Explanation: 1 has no left side, so it comes first. Then the left side of 2 (just 3), then 2 itself.
Example 2
Input: root = [1, 2, 3, 4, 5]
Output: [4, 2, 5, 1, 3]
Explanation: Left side (4, 2, 5), then the root 1, then the right side (3).
Stuck? Open one hint at a time
Hint 1
Inorder means "left side, node, right side". Record the node between the two recursive calls.
Hint 2
Without recursion: go left and push each node. When you cannot go further left, pop a node, record it, and move to its right child.
Hint 3
For O(1) extra space there is a clever trick called Morris traversal. It temporarily links the node that comes just before the current node in inorder (its "predecessor") back to the current node.
Show all 3 solutions with explanations
Approach 1Recursion
The idea

Walk left, record the node, walk right.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 inorderTraversal(root) {  const out = [];  function walk(node) {    if (node === null) return;    walk(node.left);    out.push(node.val);    walk(node.right);  }  walk(root);  return out;}console.log(inorderTraversal(buildTree([1, null, 2, 3])));  // [1, 3, 2]console.log(inorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [4, 2, 5, 1, 3]
How it works

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

Approach 2Explicit stack
The idea
  1. Keep a pointer cur and a stack.
  2. While cur exists, push it and move to its left child.
  3. When it is null, pop the top of the stack. That is the next node in order. Record it and set cur to its right child.
  4. Stop when both cur is null and the stack is empty.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 inorderTraversal(root) {  const out = [];  const stack = [];  let cur = root;  while (cur !== null || stack.length > 0) {    while (cur !== null) {      stack.push(cur);      cur = cur.left;    }    cur = stack.pop();    out.push(cur.val);    cur = cur.right;  }  return out;}console.log(inorderTraversal(buildTree([1, null, 2, 3])));  // [1, 3, 2]console.log(inorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [4, 2, 5, 1, 3]
How it works

O(n) time, O(h) space. Every node is pushed once and popped once.

Approach 3Morris traversal (O(1) extra space)
The idea
  1. If the current node has no left child, record it and go right.
  2. Otherwise find its predecessor. This is the node that comes just before it in inorder: the rightmost node of its left side.
  3. If the predecessor's right link is empty, point it back at the current node (a temporary link, like a thread) and go left.
  4. If it already points at the current node, we have just finished the left side. Remove the thread, record the current node, and go right.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 inorderTraversal(root) {  const out = [];  let cur = root;  while (cur !== null) {    if (cur.left === null) {      out.push(cur.val);      cur = cur.right;    } else {      let pred = cur.left;      while (pred.right !== null && pred.right !== cur) pred = pred.right;      if (pred.right === null) {        pred.right = cur;          // temporary link: a way back once the left side is done        cur = cur.left;      } else {        pred.right = null;         // second visit: remove the temporary link        out.push(cur.val);        cur = cur.right;      }    }  }  return out;}console.log(inorderTraversal(buildTree([1, null, 2, 3])));  // [1, 3, 2]console.log(inorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [4, 2, 5, 1, 3]
How it works

Still O(n) time (each edge, or link, is walked only a small fixed number of times). But it uses only O(1) extra space, and the tree is back to normal at the end. While it runs, it changes the tree for a short time. So it is not safe if other code reads the tree at the same moment. Know that it exists. Interviews usually expect the stack version.

Which approach should you use?

Start with recursion. Use the stack version if recursion is not allowed. Mention Morris if they ask for O(1) space. (LeetCode 94.)

Q3Binary tree postorder traversalEasy

Return the postorder traversal (the list of node values in postorder) of a binary tree.

Example 1
Input: root = [1, null, 2, 3]
Output: [3, 2, 1]
Explanation: Finish the whole side of 2 first (3, then 2), and only then the root 1.
Example 2
Input: root = [1, 2, 3, 4, 5]
Output: [4, 5, 2, 3, 1]
Explanation: Both children before their parent, all the way up.
Stuck? Open one hint at a time
Hint 1
Record the node after both recursive calls.
Hint 2
Postorder (left, right, node) written backwards is (node, right, left). That is preorder with the two children swapped.
Show all 3 solutions with explanations
Approach 1Recursion
The idea

Walk left, walk right, then record the node.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 postorderTraversal(root) {  const out = [];  function walk(node) {    if (node === null) return;    walk(node.left);    walk(node.right);    out.push(node.val);  }  walk(root);  return out;}console.log(postorderTraversal(buildTree([1, null, 2, 3])));  // [3, 2, 1]console.log(postorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [4, 5, 2, 3, 1]
How it works

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

Approach 2Reverse a modified preorder
The idea

Run a stack-based preorder that goes node, then right, then left (push left first). Reverse the output to get left, right, node.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 postorderTraversal(root) {  if (root === null) return [];  const out = [];  const stack = [root];  while (stack.length > 0) {    const node = stack.pop();    out.push(node.val);    if (node.left) stack.push(node.left);    if (node.right) stack.push(node.right);  }  return out.reverse();}console.log(postorderTraversal(buildTree([1, null, 2, 3])));  // [3, 2, 1]console.log(postorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [4, 5, 2, 3, 1]
How it works

O(n) time and space. It is simple and hard to get wrong. It records the nodes in the wrong order and fixes the order at the end.

Approach 3One stack, remember the last node visited
The idea
  1. Go left and push each node, like the stack version of inorder.
  2. Look at the top node without removing it. If it has a right child we have not handled yet, move to that child.
  3. Otherwise both sides are done. Record the node, pop it, and remember it in last.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 postorderTraversal(root) {  const out = [];  const stack = [];  let cur = root;  let last = null;                     // the node we most recently finished  while (cur !== null || stack.length > 0) {    while (cur !== null) {      stack.push(cur);      cur = cur.left;    }    const top = stack[stack.length - 1];    if (top.right !== null && top.right !== last) {      cur = top.right;                 // the right side is not done yet    } else {      out.push(top.val);      last = stack.pop();    }  }  return out;}console.log(postorderTraversal(buildTree([1, null, 2, 3])));  // [3, 2, 1]console.log(postorderTraversal(buildTree([1, 2, 3, 4, 5]))); // [4, 5, 2, 3, 1]
How it works

O(n) time, O(h) space, and the output is built in the right order. The last variable tells us that we are coming back from the right child, not arriving for the first time.

Which approach should you use?

Use recursion by default. For the stack version, the reverse-preorder trick is the easiest to remember when you are nervous. (LeetCode 145.)

Q4Maximum depth of binary treeEasy

Return the maximum depth of a binary tree: the number of nodes along the longest path from the root down to a leaf.

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: 3
Explanation: The longest path is 3, 20, 15 (three nodes).
Example 2
Input: root = [1, null, 2]
Output: 2
Explanation: A chain of two nodes.
Example 3
Input: root = []
Output: 0
Explanation: An empty tree has depth 0.
Stuck? Open one hint at a time
Hint 1
If you knew the depth of the left and right subtrees, how would you get the depth of this tree?
Hint 2
What is the depth of an empty tree?
Show all 2 solutions with explanations
Approach 1Recursion (depth from the bottom)
The idea

The depth of null is 0. The depth of a node is 1 plus the larger depth of its two children.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 maxDepth(root) {  if (root === null) return 0;  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}console.log(maxDepth(buildTree([3, 9, 20, null, null, 15, 7]))); // 3console.log(maxDepth(buildTree([1, null, 2])));                  // 2console.log(maxDepth(buildTree([])));                            // 0
How it works

O(n) time, O(h) space. Each node asks its children for their answers and then adds itself. This is postorder thinking: children first, then the node.

Approach 2Explicit stack carrying the depth
The idea

Push [node, depth] pairs. Each time you pop a node, update the best depth seen so far. Then push its children with depth + 1.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 maxDepth(root) {  if (root === null) return 0;  let best = 0;  const stack = [[root, 1]];  while (stack.length > 0) {    const [node, depth] = stack.pop();    best = Math.max(best, depth);    if (node.left) stack.push([node.left, depth + 1]);    if (node.right) stack.push([node.right, depth + 1]);  }  return best;}console.log(maxDepth(buildTree([3, 9, 20, null, null, 15, 7]))); // 3console.log(maxDepth(buildTree([1, null, 2])));                  // 2console.log(maxDepth(buildTree([])));                            // 0
How it works

O(n) time. Here the depth travels down with each stack entry, instead of coming back up from the recursion. It also works for very deep trees.

Which approach should you use?

Use the two-line recursion. (LeetCode 104.) Lesson 42 adds a third way: count the levels with a queue.

Q5Invert binary treeEasy

Invert a binary tree (swap the left and right child of every node) and return its root.

Example 1
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]
Explanation: At every node the left and right children swap places, so the tree becomes its mirror image (like looking at it in a mirror).
Example 2
Input: root = [2, 1, 3]
Output: [2, 3, 1]
Explanation: Only the root has children to swap.
Example 3
Input: root = []
Output: []
Explanation: Nothing to invert.
Stuck? Open one hint at a time
Hint 1
What does one node have to do? Swap its two children.
Hint 2
Is it enough to swap at the root only? No. The children must be inverted too.
Show all 2 solutions with explanations
Approach 1Recursion
The idea
  1. If the node is null, return null.
  2. Invert the left side and the right side.
  3. Put the inverted right side on the left, and the inverted left side on the right.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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;}// Tree -> level-order array with null gaps (trailing nulls trimmed), for printing.function toList(root) {  const out = [], queue = [root];  let head = 0;  while (head < queue.length) {    const node = queue[head++];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length > 0 && out[out.length - 1] === null) out.pop();  return out;}function invertTree(root) {  if (root === null) return null;  const left = invertTree(root.left);  const right = invertTree(root.right);  root.left = right;  root.right = left;  return root;}console.log(toList(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9])))); // [4, 7, 2, 9, 6, 3, 1]console.log(toList(invertTree(buildTree([2, 1, 3]))));             // [2, 3, 1]console.log(toList(invertTree(buildTree([]))));                    // []
How it works

O(n) time, O(h) space. It changes the tree itself (no copy) and returns the same root.

Approach 2Explicit stack
The idea

Pop a node, swap its children, then push the children that exist. The order does not matter, because every node only needs its own swap.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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;}// Tree -> level-order array with null gaps (trailing nulls trimmed), for printing.function toList(root) {  const out = [], queue = [root];  let head = 0;  while (head < queue.length) {    const node = queue[head++];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length > 0 && out[out.length - 1] === null) out.pop();  return out;}function invertTree(root) {  if (root === null) return null;  const stack = [root];  while (stack.length > 0) {    const node = stack.pop();    const left = node.left;    node.left = node.right;    node.right = left;    if (node.left) stack.push(node.left);    if (node.right) stack.push(node.right);  }  return root;}console.log(toList(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9])))); // [4, 7, 2, 9, 6, 3, 1]console.log(toList(invertTree(buildTree([2, 1, 3]))));             // [2, 3, 1]
How it works

O(n) time, O(h) space. Any walking order works, including the queue-based one from the next lesson.

Which approach should you use?

Use recursion. The code reads just like the definition. (LeetCode 226.)

Q6Same treeEasy

You get the roots of two binary trees p and q. Return whether they are the same: same shape and same values.

Example 1
Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Explanation: Same shape, same values.
Example 2
Input: p = [1, 2], q = [1, null, 2]
Output: false
Explanation: The values are the same, but 2 is a left child in p and a right child in q.
Example 3
Input: p = [1, 2, 1], q = [1, 1, 2]
Output: false
Explanation: The shape is the same, but the values of the children differ.
Stuck? Open one hint at a time
Hint 1
Compare two nodes at a time, one from each tree, and walk both trees together.
Hint 2
A pair of nodes has three cases: both are null, exactly one is null, or neither is null.
Show all 3 solutions with explanations
Approach 1Turn both into text and compare (brute force)
The idea

Turn each tree into a string of text in preorder. Write a marker for every missing child, so the shape is kept too. Equal strings mean equal trees.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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(node) {  if (node === null) return "#";  return node.val + "," + serialize(node.left) + "," + serialize(node.right);}function isSameTree(p, q) {  return serialize(p) === serialize(q);}console.log(isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 3])));       // trueconsole.log(isSameTree(buildTree([1, 2]), buildTree([1, null, 2])));       // falseconsole.log(isSameTree(buildTree([1, 2, 1]), buildTree([1, 1, 2])));       // false
How it works

O(n) time and extra space for the strings. Without the # markers, [1,2] and [1,null,2] would look the same, so the markers are a must. The answer is correct but wasteful. It builds both strings even if the roots already differ.

Approach 2Recursion, walking both trees together
The idea
  1. Both are null: they are the same.
  2. Only one is null: they are different.
  3. Otherwise the two values must be equal, and both pairs of children must be the same.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 isSameTree(p, q) {  if (p === null && q === null) return true;  if (p === null || q === null) return false;  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}console.log(isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 3])));       // trueconsole.log(isSameTree(buildTree([1, 2]), buildTree([1, null, 2])));       // falseconsole.log(isSameTree(buildTree([1, 2, 1]), buildTree([1, 1, 2])));       // false
How it works

O(n) time, O(h) space. It stops at the first difference, because && skips the rest as soon as one part is false.

Approach 3Explicit stack of pairs
The idea

Push the pair of roots. Pop a pair and run the same three checks. Then push the left pair and the right pair.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 isSameTree(p, q) {  const stack = [[p, q]];  while (stack.length > 0) {    const [a, b] = stack.pop();    if (a === null && b === null) continue;    if (a === null || b === null || a.val !== b.val) return false;    stack.push([a.left, b.left], [a.right, b.right]);  }  return true;}console.log(isSameTree(buildTree([1, 2, 3]), buildTree([1, 2, 3])));       // trueconsole.log(isSameTree(buildTree([1, 2]), buildTree([1, null, 2])));       // falseconsole.log(isSameTree(buildTree([1, 2, 1]), buildTree([1, 1, 2])));       // false
How it works

The same logic with your own stack: O(n) time, O(h) space.

Which approach should you use?

Use the recursion. It is the clearest. (LeetCode 100.) The same idea of walking two nodes together comes back in lesson 43 for symmetric trees and subtrees.

Q7Leaf-similar treesEasy

The leaf value sequence of a tree is the list of its leaf values, read from left to right. Two trees are leaf-similar if their lists are equal. Return whether root1 and root2 are leaf-similar.

Example 1
Input: root1 = [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4], root2 = [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8]
Output: true
Explanation: Both leaf lists, read left to right, are 6, 7, 4, 9, 8, even though the trees have different shapes.
Example 2
Input: root1 = [1, 2, 3], root2 = [1, 3, 2]
Output: false
Explanation: The leaf lists are 2, 3 and 3, 2. The order matters.
Stuck? Open one hint at a time
Hint 1
A leaf is a node with no children. In which walking order do you meet the leaves from left to right?
Hint 2
Any depth-first order meets the leaves from left to right, as long as you explore the left side before the right side.
Show all 2 solutions with explanations
Approach 1Collect both leaf lists, then compare
The idea

Walk each tree and add the value of every leaf to an array. Then compare the two arrays item by item.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 leaves(node, out = []) {  if (node === null) return out;  if (node.left === null && node.right === null) out.push(node.val);  leaves(node.left, out);  leaves(node.right, out);  return out;}function leafSimilar(root1, root2) {  const a = leaves(root1), b = leaves(root2);  return a.length === b.length && a.every((v, i) => v === b[i]);}console.log(leafSimilar(  buildTree([3, 5, 1, 6, 2, 9, 8, null, null, 7, 4]),  buildTree([3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8]),)); // trueconsole.log(leafSimilar(buildTree([1, 2, 3]), buildTree([1, 3, 2]))); // false
How it works

O(n + m) time and space for the two lists.

Approach 2Get leaves one at a time, only when needed
The idea

Give each tree its own stack and a helper that returns the next leaf, using the stack-based preorder from this lesson. Compare the leaves as they come. Stop at the first mismatch.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    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 nextLeaf(stack) {  while (stack.length > 0) {    const node = stack.pop();    if (node.left === null && node.right === null) return node.val;    if (node.right) stack.push(node.right);    if (node.left) stack.push(node.left);  }  return undefined;                       // no more leaves}function leafSimilar(root1, root2) {  const s1 = root1 ? [root1] : [];  const s2 = root2 ? [root2] : [];  while (true) {    const a = nextLeaf(s1), b = nextLeaf(s2);    if (a !== b) return false;    if (a === undefined) return true;     // both ran out together  }}console.log(leafSimilar(  buildTree([3, 5, 1, 6, 2, 9, 8, null, null, 7, 4]),  buildTree([3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8]),)); // trueconsole.log(leafSimilar(buildTree([1, 2, 3]), buildTree([1, 3, 2]))); // false
How it works

O(n + m) time in the worst case, but it can stop early. The extra space is only the two stacks (O(h)), not two full lists.

Which approach should you use?

Collecting the lists is simpler and fine for interviews. Mention the one-leaf-at-a-time version as a way to make it faster. (LeetCode 872.)

Make it stick

Make it stick — close this page, then
  1. Define root, leaf, subtree, depth and height, and say what a binary tree is.
  2. Say where the line that records the node sits in preorder, inorder and postorder.
  3. Explain why the extra space of a recursive walk is O(h), and when h is as big as n.
  4. Write iterative preorder and inorder with a stack, without looking.
  5. Explain why the recursive solution always starts with the null check.

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

Depth-first goes deep before it goes wide. Lesson 42 does the opposite. Level order, also called breadth-first search, visits the tree row by row with a queue. It helps with right side views, zigzag orders and the shortest path to a leaf.

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