const BST = {
createNode (value) {
const node = {
value,
left: null,
right: null
}
return node
},
create (...values) {
const first = values.shift()
const tree = BST.createNode(first)
const insertNode = (value, node) => {
let current = node
if (value < current.value) {
if (current.left) {
insertNode(value, current.left)
} else {
current.left = BST.createNode(value)
}
} else {
if (current.right) {
insertNode(value, current.right)
} else {
current.right = BST.createNode(value)
}
}
}
const walkPreOrder = (root, visitor) => {
if (!root) {
return
}
visitor(root)
if (root.left) {
walkPreOrder(root.left, visitor)
}
if (root.right) {
walkPreOrder(root.right, visitor)
}
}
const walkInOrder = (root, visitor) => {
if (!root) {
return
}
if (root.left) {
walkInOrder(root.left, visitor)
}
visitor(root)
if (root.right) {
walkInOrder(root.right, visitor)
}
}
const walkPostOrder = (root, visitor) => {
if (!root) {
return
}
if (root.left) {
walkPostOrder(root.left, visitor)
}
if (root.right) {
walkPostOrder(root.right, visitor)
}
visitor(root)
}
const walkLevelOrder = (root, visitor) => {
const q = [root]
while (q.length) {
const node = q.shift()
if (node) {
visitor(node)
if (node.left) {
q.push(node.left)
}
if (node.right) {
q.push(node.right)
}
}
}
}
values.forEach(value => insertNode(value, tree))
return {
root: tree,
// Depth-First-Search - DFS
preOrder: visitor => walkPreOrder(tree, visitor),
inOrder: visitor => walkInOrder(tree, visitor),
postOrder: visitor => walkPostOrder(tree, visitor),
// Breadth-First-Search - BFS
levelOrder: visitor => walkLevelOrder(tree, visitor)
}
}
}
const values = [8, 3, 1, 6, 4, 7, 10, 14, 13]
const {
root,
// preOrder: walk,
// inOrder: walk,
postOrder: walk,
// levelOrder: walk
} = BST.create(...values)
// console.log(JSON.stringify(root, null, 2))
const out = []
walk(node => { out.push(node.value) })
console.log(out.join(' -> '))
// pre order
// 8 -> 3 -> 1 -> 6 -> 4 -> 7 -> 10 -> 14 -> 13
// in order
// 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14
// post order
// 1 -> 4 -> 7 -> 6 -> 3 -> 13 -> 14 -> 10 -> 8
// level order
// 8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13
// use pre order for copying a tree
// use in order for a sorted tree
// use post order when deleting a tree
// *level order is not typically used with BST but exists here for example