Recursion and trees · Lesson 17 of 23
Binary search trees
An ordered tree: search and insert in O(h), and inorder visits values in sorted order.
A BST is a binary tree with a rule: everything on the left is smaller than the node and everything on the right is larger, at every node. Searching resembles binary search: each step picks a side and ignores the other.
class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
function insert(root, val) {
if (!root) return new TreeNode(val)
if (val < root.val) root.left = insert(root.left, val)
else root.right = insert(root.right, val)
return root
}
function contains(root, val) {
let node = root
while (node) {
if (val === node.val) return true
node = val < node.val ? node.left : node.right
}
return false
}
const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out) } return out }
let root = null
for (const v of [50, 30, 70, 20, 40, 60, 80]) root = insert(root, v)
console.log(contains(root, 60), contains(root, 65))
console.log(inorder(root).join(" "))- 50
- 30
- 20
- 40
- 70
- 60
- 80
- 30
Searching 60: larger than 50 → right, smaller than 70 → left, found. Only three comparisons.
What's the output?
class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
function insert(r, v) { if (!r) return new TreeNode(v); if (v < r.val) r.left = insert(r.left, v); else r.right = insert(r.right, v); return r }
const depth = (n) => (n ? 1 + Math.max(depth(n.left), depth(n.right)) : 0)
let a = null, b = null
for (const v of [1, 2, 3, 4, 5]) a = insert(a, v)
for (const v of [3, 1, 4, 2, 5]) b = insert(b, v)
console.log(depth(a), depth(b))What will this code print?
Spot the bug
This checks for a BST, but returns true for an invalid tree like [5, 1, 7, null, null, 3, 8] (3 sits in 5's right subtree). Which line is the problem?
Exercise
Write rangeSum(root, lo, hi) summing values between lo and hi (inclusive), using the BST order to skip useless branches. It must print 150 0.
Expected output: 150 0
class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r } }
function insert(r, v) { if (!r) return new TreeNode(v); if (v < r.val) r.left = insert(r.left, v); else r.right = insert(r.right, v); return r }
let root = null
for (const v of [50, 30, 70, 20, 40, 60, 80]) root = insert(root, v)
function rangeSum(root, lo, hi) {
}
console.log(rangeSum(root, 40, 60), rangeSum(root, 81, 99))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 3 games
Sign in to save your progress and earn XP.