Binary Tree Traversals

binary-tree-traversals.js

/**
 * @typedef {object} TreeNode
 * @property {number} val
 * @property {Node} left
 * @property {Node} right
 */
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

const n46 = new TreeNode(46, null, null)
const n54 = new TreeNode(54, null, null)
const n35 = new TreeNode(35, null, null)
const n45 = new TreeNode(45, null, n46)
const n55 = new TreeNode(55, n54, null)
const n65 = new TreeNode(65, null, null)
const n40 = new TreeNode(40, n35, n45)
const n60 = new TreeNode(60, n55, n65)
const n50 = new TreeNode(50, n40, n60)
const root = n50

/**
                            50
            40                              60
    35              45              55              65
                        46      54


50, 40, 60, 35, 45, 55, 65, 46, 54
*/

/**
 * Pre order traversal is using nodes as soon as you get them, pushing
 * right to stack, then left.
 * @param {TreeNode} root
 */
function preOrderTraversal (root) {
    let stack = [ root ]
    let arr = []

    while (stack.length) {
        let node = stack.pop()
        arr.push(node.val)
        node.right && stack.push(node.right)
        node.left && stack.push(node.left)
    }

    return arr.join(', ')
}

/**
 * In order is move left while possible, pushing nodes to stack.
 * Then, pop from stack and move right.
 * @param {TreeNode} root
 */
function inOrderTraversal(node) {
    let stack = []
    let arr = []

    while (stack.length || node !== null) {
        if (node !== null) {
            stack.push(node)
            node = node.left
        } else {
            node = stack.pop()
            arr.push(node.val)
            node = node.right
        }
    }

    return arr.join(', ')
}

/**
 * Post order is move right while possible, pushing nodes to stack.
 * Then, pop from stack and move left.
 * @param {TreeNode} root
 */
function postOrderTraversal(node) {
    let stack = []
    let arr = []

    while (stack.length > 0 || node !== null) {
        if (node !== null) {
            stack.push(node)
            node = node.right
        } else {
            node = stack.pop()
            arr.push(node.val)
            node = node.left
        }
    }

    return arr.join(', ')
}

console.log({label: 'pre-order ', data: preOrderTraversal(root)})
console.log({label: 'in-order  ', data: inOrderTraversal(root)})
console.log({label: 'post-order', data: postOrderTraversal(root)})

// { label: 'pre-order ', data: '50, 40, 35, 45, 46, 60, 55, 54, 65' }
// { label: 'in-order  ', data: '35, 40, 45, 46, 50, 54, 55, 60, 65' }
// { label: 'post-order', data: '65, 60, 55, 54, 50, 46, 45, 40, 35' }