Good morning! Here's our prompt for today.
A binary search tree is a data structure that has the following properties,
- Each node in the tree has only two children.
- The left subtree consists of nodes with values less than the root node.
- The right subtree consists of nodes with values greater than the root node.
Consider that you are given a binary search tree as root, and two integers low and high. Can you find the sum of values of all nodes that are in the inclusive range [low, high]?
This problem can be best understood visually. Consider the example below. Nodes with values between the [7, 15] range are colored orange, and the sum of values of these nodes gives us the answer.
Constraints
- The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 1051 <= low <= high <= 105- All
Node.valare unique.
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx69
var assert = require('assert');function TreeNode(val) { this.val = val this.left = null this.right = null}/** * @param {TreeNode} root * @param {number} low * @param {number} high * @return {number} */function sumRangeBST(root, low, high) { return}try { let root = new TreeNode(10) root.left = new TreeNode(5) root.right = new TreeNode(15) root.left.left = new TreeNode(3) root.left.right = new TreeNode(7) root.right.right = new TreeNode(18) assert.equal(sumRangeBST(root, 7, 15), 32); console.log('PASSED: ' + "sumRangeBST([10, 5, 15, 3, 7, None, 18], 7, 15) should return `32`");} catch (err) { console.log(err);}try { let root = new TreeNode(10) root.left = new TreeNode(5) root.right = new TreeNode(15) root.left.left = new TreeNode(3) root.left.right = new TreeNode(7) root.right.left = new TreeNode(13) root.right.right = new TreeNode(18) root.left.left.left = new TreeNode(1) root.left.right.left = new TreeNode(6) assert.equal(sumRangeBST(root, 6, 10), 23); console.log('PASSED: ' + "sumRangeBST([10, 5, 15, 3, 7, 13, 18, 1, None, 6], 6, 10) should return `23`");} catch (err) { console.log(err);}try { let root = new TreeNode(9) assert.equal(sumRangeBST(root, 0, 9), 9); console.log('PASSED: ' + "sumRangeBST([9], 0, 9) should return `9`");} catch (err) { console.log(err);}try { let root = new TreeNode(12) root.left = new TreeNode(6) root.right = new TreeNode(18) assert.equal(sumRangeBST(root, 1, 5), 0); console.log('PASSED: ' + "sumRangeBST([12, 6, 18], 1, 5) should return `0`");} catch (err) { console.log(err);}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's our guided, illustrated walk-through.
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.
