Recursion and trees · Lesson 16 of 23

Binary trees

Nodes and children, depth-first visits (pre/in/post-order) and level-order (BFS).

15 minutes2 games

A binary tree is made of nodes, each with a left and a right child (or null). The top node is the root; nodes without children are leaves.

Trees are everywhere: the DOM, file systems, nested JSON, and databases (B-trees).

1
- 2
  - 4
  - 5
- 3
  - 6

Preorder: 1 2 4 5 3 6 · Inorder: 4 2 5 1 6 3 · Postorder: 4 5 2 6 3 1 · Level order: 1 2 3 4 5 6

JavaScript

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6)))

// Depth-first: the only difference is WHEN we record the node
const pre = [], ino = [], post = []
function dfs(node) {
  if (!node) return
  pre.push(node.val)      // before the children
  dfs(node.left)
  ino.push(node.val)      // between them
  dfs(node.right)
  post.push(node.val)     // after them
}
dfs(root)
console.log(pre.join(" "), "|", ino.join(" "), "|", post.join(" "))

// Breadth-first: level by level with a queue
const levels = []
let level = [root]
while (level.length) {
  levels.push(level.map((n) => n.val))
  level = level.flatMap((n) => [n.left, n.right].filter(Boolean))
}
console.log(levels)

Most tree problems = "ask your children"

Most problems follow one shape: the function asks the left and right children (recursion) and combines their answers with the node's value. Depth? 1 + max(left, right). Sum? val + left + right. Symmetric? Compare left with right, mirrored.

JavaScript

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
const depth = (n) => (n ? 1 + Math.max(depth(n.left), depth(n.right)) : 0)
const sum = (n) => (n ? n.val + sum(n.left) + sum(n.right) : 0)
const leaves = (n) => (!n ? 0 : !n.left && !n.right ? 1 : leaves(n.left) + leaves(n.right))

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6)))
console.log(depth(root), sum(root), leaves(root))

Quick question

You want the values seen from the right side (the last node of each level). The most natural approach?

Exercise

Write countGreater(root, x) counting nodes whose value is greater than x. It must print 3 0.

Expected output: 3 0

JavaScript

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
const root = new TreeNode(5, new TreeNode(3, new TreeNode(8)), new TreeNode(9, null, new TreeNode(1)))

function countGreater(root, x) {
  
}

console.log(countGreater(root, 4), countGreater(root, 10))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 2 games

DSA

Recursion and trees · Lesson 16 of 23

Binary trees

Nodes and children, depth-first visits (pre/in/post-order) and level-order (BFS).

15 minutes2 games

A binary tree is made of nodes, each with a left and a right child (or null). The top node is the root; nodes without children are leaves.

Trees are everywhere: the DOM, file systems, nested JSON, and databases (B-trees).

1
- 2
  - 4
  - 5
- 3
  - 6

Preorder: 1 2 4 5 3 6 · Inorder: 4 2 5 1 6 3 · Postorder: 4 5 2 6 3 1 · Level order: 1 2 3 4 5 6

JavaScript

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6)))

// Depth-first: the only difference is WHEN we record the node
const pre = [], ino = [], post = []
function dfs(node) {
  if (!node) return
  pre.push(node.val)      // before the children
  dfs(node.left)
  ino.push(node.val)      // between them
  dfs(node.right)
  post.push(node.val)     // after them
}
dfs(root)
console.log(pre.join(" "), "|", ino.join(" "), "|", post.join(" "))

// Breadth-first: level by level with a queue
const levels = []
let level = [root]
while (level.length) {
  levels.push(level.map((n) => n.val))
  level = level.flatMap((n) => [n.left, n.right].filter(Boolean))
}
console.log(levels)

Most tree problems = "ask your children"

JavaScript

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
const depth = (n) => (n ? 1 + Math.max(depth(n.left), depth(n.right)) : 0)
const sum = (n) => (n ? n.val + sum(n.left) + sum(n.right) : 0)
const leaves = (n) => (!n ? 0 : !n.left && !n.right ? 1 : leaves(n.left) + leaves(n.right))

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6)))
console.log(depth(root), sum(root), leaves(root))

Quick question

You want the values seen from the right side (the last node of each level). The most natural approach?

Exercise

Write countGreater(root, x) counting nodes whose value is greater than x. It must print 3 0.

Expected output: 3 0

JavaScript

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
const root = new TreeNode(5, new TreeNode(3, new TreeNode(8)), new TreeNode(9, null, new TreeNode(1)))

function countGreater(root, x) {
  
}

console.log(countGreater(root, 4), countGreater(root, 10))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 2 games