As part of the Algorithms and Data Structures series, I am covering Binary Search and Binary Search Tree. I go into detail about the difference between each, and when to recognise which one to use when faced with a question.
The structure of a Binary Tree includes three parts, a node, a left pointer and a right pointer.
Within the Binary Tree, subtrees can have zero to two nodes.
The depth of a node is the distance from the root node to a particular node of which the depth is being measured.
The height of the tree is the longest distance from the root node to the lead node.
Write a function that takes in a Binary Tree and returns a list of its branch sums ordered from leftmost branch sum to rightmost branch sum.
A branch sum is the sum of all values in a Binary Tree branch. A Binary Tree branch is a path of nodes in a tree that starts at the root node and ends at any leaf node.
Each BinaryTree node has an integer value, a left child node and a right child node. Children nodes can either be BinaryTree nodes themselves or none/null.
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10[15, 16, 18, 10, 11]
// 15 == 1 + 2 + 4 + 8
// 16 == 1 + 2 + 4 + 9
// 18 == 1 + 2 + 5 + 10
// 10 == 1 + 3 + 6
// 11 == 1 + 3 + 7class BinaryTree {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function branchSums(root) {}class BinaryTree {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function branchSums(root) {
return branchSumsHelper(root, root.value);
}
function branchSumsHelper(root, subTotal, total = []) {
if (!root) return;
if (!root.left && !root.right) total.push(subTotal);
if (root.left) branchSumsHelper(root.left, subTotal + root.left.value, total);
if (root.right)
branchSumsHelper(root.right, subTotal + root.right.value, total);
return total;
}Write a function that takes a Binary Tree and returns its diameter. The diameter of a binary tree is defined as the length of its longest path, even if that path doesn’t pass through the root of the tree.
A path is a collection of connected nodes in a tree, where no node is connected to more than two other nodes. The length of a path is the number of edges between the path’s first node and it’s last node.
Each BinaryTree node has an integer value, a left child node and a right child node. Children nodes can either be BinaryTree nodes themselves or none/null.
1
/ \
3 2
/ \
7 4
/ \
8 5
/ \
9 66 // 9 -> 8 -> 7 -> 3 -> 4 -> 5 -> 6
// There are 6 edges between the first node and the last node of this tree's longest pathclass BinaryTree {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function binaryTreeDiameter(tree) {
return -1;
}// This is an input class. Do not edit.
class BinaryTree {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function calcDiameter(tree, diameter) {
if (!tree) return 0;
const leftCount = calcDiameter(tree.left, diameter);
const rightCount = calcDiameter(tree.right, diameter);
diameter.max = Math.max(leftCount + rightCount, diameter.max);
return Math.max(leftCount + 1, rightCount + 1);
}
function binaryTreeDiameter(tree) {
const diameter = { max: -Infinity };
calcDiameter(tree, diameter);
return diameter.max;
}Write a function that takes in a Binary Tree and returns its max path sum.
A path is a collection of connected nodes in a tree, where no node is connected to more than two other nodes; a path sum is the sum of the values of the nodes in a particular path.
Each BinaryTree node has an integer value, a left child node and a right child node. Children nodes can either be BinaryTree nodes themselves or none/null.
1
/ \
2 3
/ \ / \
4 5 6 718 // 5 + 2 + 1 + 3 + 7function maxPathSum(tree) {}function maxPathSum(tree) {
let max = -Infinity;
const dfs = (node) => {
if (!node) return 0;
const left = dfs(node.left);
const right = dfs(node.right);
max = Math.max(max, left + right + node.value);
return Math.max(node.value + Math.max(left, right), 0);
};
dfs(tree);
return max;
}The structure of a Binary Tree includes three parts, a node, a left pointer and a right pointer.
Within a Binary Search Tree, subtrees have two nodes, the left node must be of a value less than the right node.
class Node {
constructor(val) {
this.val = val
this.right, this.left = null
}
}
class BST {
constructor(val) {
this.root = new Node(value)
this.count = 1
}
size() {
return this.count
}
insert(value) {
this.count++
let newNode = new Node(value)
const searchTree = (node) => {
if(value < node.value) {
if(!node.left) {
node.left = newNode
} else {
searchTree(node.left)
}
else if(value > node.value) {
if(!node.right) {
node.right = newNode
} else {
searchTree(node.right)
}
}
}
searchTree(this.root)
}
min() {
let currentNode = this.root
while(currentNode.left) {
currentNode = currentNode.left
}
return currentNode.value
}
max() {
let currentNode = this.root
while(currentNode.right) {
currentNode = currentNode.right
}
return currentNode.value
}
containts(value) {
let currentNode = this.root
while(currentNode) {
if(value === currentNode.value) {
return true
}
if(value < currentNode.value) {
currentNode = currentNode.left
} else {
currentNode = currentNode.right
}
return false
}
}
}
}Left, root, right
inOrder() {
let result = []
const traverse = (node) => {
if(node.left) traverse(node.left)
result.push(node.value)
if(node.right) traverse(node.right)
}
traverse(this.root)
return result
}Root, left, right
preOrder() {
let result = []
const traverse = (node) => {
result.push(node.value)
if(node.left) traverse(node.left)
if(node.right) traverse(node.right)
}
traverse(this.root)
return result
}Left, right, root
postOrder() {
let result = []
const traverse = (node) => {
if(node.left) traverse(node.left)
if(node.right) traverse(node.right)
result.push(node.value)
}
traverse(this.root)
return result
}Level by level
Reminder: use a queue
bfs() {
let result = []
let queue = []
queue.push(this.root)
while(queue.length) {
let currentNode = queue.shift()
result.push(currentNode.value)
if(currentNode.left) {
queue.push(currentNode.left)
}
if(currentNode.right) {
queue.push(currentNode.right)
}
}
return result
}Write a function that takes in a Binary Search Tree (BST) and a target integer value and returns the cloest value to that target value contained in the BST.
You can assume that there will only be one cloest value.
10
/ \
5 15
/ \ / \
2 5 13 22
/ \
1 14
target = 1213function findClosestValueInBst(tree, target) {}
// This is the class of the input tree. Do not edit.
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}function findClosestValueInBst(tree, target) {
return findClosestValueInBstHelper(tree, target, tree.value);
}
function findClosestValueInBstHelper(tree, target, closest) {
let currentNode = tree;
while (currentNode) {
if (Math.abs(target - closest) > Math.abs(target - currentNode.value)) {
closest = currentNode.value;
}
if (target < currentNode.value) {
currentNode = currentNode.left;
} else if (target > currentNode.value) {
currentNode = currentNode.right;
} else {
break;
}
}
return closest;
}
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}Write three functions that take in a Binary Search Tree and an empty array, traverse the BST, add its nodes’ values to the input array, and return the array. The three functons should traverse the BST using the in-order, pre-order and post-order tree traversal techniques, respectively.
10
/ \
5 15
/ \ \
2 5 22
/
1
array = []inOrderTraverse: [1, 2, 5, 5, 10, 15, 22]
preOrderTraverse: [10, 5, 2, 1, 5, 15, 22]
postOrderTraverse: [1, 2, 5, 5, 22, 15, 10]function inOrderTraverse(tree, array) {
// Write your code here.
}
function preOrderTraverse(tree, array) {
// Write your code here.
}
function postOrderTraverse(tree, array) {
// Write your code here.
}function inOrderTraverse(tree, array) {
// left, root, right
if (!tree) return array;
inOrderTraverse(tree.left, array);
array.push(tree.value);
inOrderTraverse(tree.right, array);
return array;
}
function preOrderTraverse(tree, array) {
// root, left, right
if (!tree) return array;
array.push(tree.value);
preOrderTraverse(tree.left, array);
preOrderTraverse(tree.right, array);
return array;
}
function postOrderTraverse(tree, array) {
// left, right, root
if (!tree) return array;
postOrderTraverse(tree.left, array);
postOrderTraverse(tree.right, array);
array.push(tree.value);
return array;
}You’re given three nodes that are contained in the same Binary Search Tree: nodeOne, nodeTwo and nodeThree. Write a function that returns a boolean representing whether one of nodeOne or nodeThree is an ancestor of nodeTwo. and the other node is a descendant of nodeTwo.
A descendant of a node N is defined as a node contained in the tree rooted at N. A node N is an ancestor of another node M if M is a descendant of N.
5
/ \
2 7
/ \ / \
1 4 6 8
/ /
0 3
nodeOne = 5
nodeTwo = 2
nodeThree = 3true // nodeOne is an ancestor of nodeTwo, and nodeThree is a descendant of nodeTwoclass BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function validateThreeNodes(nodeOne, nodeTwo, nodeThree) {
// Write your code here.
return false;
}class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function validateThreeNodes(nodeOne, nodeTwo, nodeThree) {
if (desc(nodeTwo, nodeOne)) return desc(nodeThree, nodeTwo);
if (desc(nodeTwo, nodeThree)) return desc(nodeOne, nodeTwo);
return false;
}
function desc(node, target) {
while (node !== null && node !== target) {
node = target.value < node.value ? node.left : node.right;
}
return node === target;
}