How to implement a binary tree? | Part 2

By Prajwal Haniya

Techletter #29 | May 23, 2023

Let’s implement a binary tree using JavaScript.

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

The above class is a fundamental building block for implementing a binary tree. It represents a single node within the tree

class BinaryTree {
    constructor() {
        this.root = null;
    }
    
    insertValue(value) {
        const newNode = new TreeNode(value);
        if (this.root == null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left == null) {
                node.left == newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right == null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
    
    // Traverse the array 
}

Now let’s traverse the binary tree

class BinaryTree {
    // all the methods above
    inorderTraversal() {
        this.inorderTraversalNode(this.root);
    }
    
    inorderTraversalNode(node) {
        if (node != null) {
            this.inorderTraversalNode(node.left);
            console.log(node.value);
            this.inorderTraversalNode(node.right)
        }
    }
    
}

Inorder Traversal: Left, Root, Right

Preorder Traversal: Root, Left, Right

Postorder Traversal: Left, Right, Root

So, basically knowing one traversal, you can easily write methods for other traversals, as it’s only how you console the value that matters.

You can test the above code using the following:

const tree = new BinaryTree();

tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(4);
tree.insert(6);
tree.insert(8);

// Perform an inorder traversal and print each node's value
tree.inorderTraversal(value => console.log(value));