Skip to content

Instantly share code, notes, and snippets.

@juliovedovatto
Last active January 21, 2021 00:53
Show Gist options
  • Save juliovedovatto/bcbb612539d6551017f3e31c39319c2a to your computer and use it in GitHub Desktop.
Save juliovedovatto/bcbb612539d6551017f3e31c39319c2a to your computer and use it in GitHub Desktop.
JS Basic Binary Tree exercise
/**
* Binary Tree Exercise
*
* Given a binary tree, similar to shape as below, write an algorithm
* to count the number of times each `value` appears.
*
* Assumptions:
*
* 1. each node will have a `value` prop
* 2. each node may or may not have a `left` prop
* 3. each node may or may not have a `right` prop
*
* Expected output for the given tree:
*
* { tacos: 3, salad: 2, pizza: 2 }
*/
const tree = {
left: {
right: {
value: 'tacos'
},
value: 'salad'
},
right: {
left: {
left: {
right: {
value: 'pizza'
},
value: 'salad'
},
value: 'tacos'
},
value: 'pizza'
},
value: 'tacos'
}
function countTree(node, accumulator = {}) {
let obj = Object.keys(accumulator).length ? accumulator : {}
if (node.left) {
obj = countTree(node.left, obj)
}
if (node.right) {
obj = countTree(node.right, obj)
}
if (node.value) {
obj[node.value] = obj[node.value] ? obj[node.value] + 1 : 1
}
return obj
}
console.log(countTree(tree)) // { tacos: 3, salad: 2, pizza: 2 }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment