Approaching Various Tree Algorithm using Javascript



This content originally appeared on DEV Community and was authored by Ashutosh Sarangi

Simple Tree

  1. we need to always start with the simple one then step by step we can go to the complex Algorithm.
  • Simple Tree
  • Binary Tree
class SimpleTree {
    constructor(value) {
        this.value = value;
        this.children = [];
    }

    insertChild(value) {
        const newChild = new SimpleTree(value);
        const lastElement = this.findLastChild(this);
        lastElement.children.push(newChild);

        return newChild;
    }

    findLastChild(root) {
        if (root.children.length == 0) {
            return root;
        }
        return this.findLastChild(root.children[0]);
    }

    traversal(root) {
        console.log(root.value + ' --> ');
        root.children.forEach(child => {
            this.traversal(child);
        })
    }
}

const simpleTree = new SimpleTree('A');
simpleTree.insertChild('B');
simpleTree.insertChild('C');
simpleTree.insertChild('D');
simpleTree.insertChild('E');
simpleTree.insertChild('F');

console.log(simpleTree)
simpleTree.traversal(simpleTree)

/*
{
    "value": "A",
    "children": [
        {
            "value": "B",
            "children": [
                {
                    "value": "C",
                    "children": [
                        {
                            "value": "D",
                            "children": [
                                {
                                    "value": "E",
                                    "children": [
                                        {
                                            "value": "F",
                                            "children": []
                                        }
                                    ]
                                }
                            ]
                        }
                    ]
                }
            ]
        }
    ]
}
*/

Binary Tree

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

    insertNode(value) {
        const newNode = new BinaryTree(value);
        const {node: lastNode, side} = this.findAppropriatePlace(this, value);
        lastNode[side] = newNode;

        return newNode;
    }

    removeFromNode(value) {
       this.findAppropriateNodAndrRemove(this, value);
    }

    findAppropriateNodAndrRemove(root, value) {
        const side = root.value < value ? 'right' : 'left';

        if (root[side].value == value) {
            root[side] = null;
            return ;
        }

        return this.findAppropriateNodAndrRemove(root[side], value);
    }
    // root left right
    preOrderTraversal(root) {
        if (root === null) {
            return ;
        }
        console.log(root.value);
        this.preOrderTraversal(root.left);
        this.preOrderTraversal(root.right);
    }

    inOrderTraversal(root) {
        // left root right
         if (root === null) {
            return ;
        }
        this.inOrderTraversal(root.left);
        console.log(root.value);
        this.inOrderTraversal(root.right);
    }

    // left right root
    postOrderTraversal(root){
         if (root === null) {
            return ;
        }
        this.postOrderTraversal(root.left);
        console.log(root.value);
        this.postOrderTraversal(root.right)
    }

    findAppropriatePlace(root, value) {
        const side = root.value < value ? 'right' : 'left';

        if (side !== '' && root[side] === null) {
            return {node : root, side};
        }
        if(root.value < value) {
            //right
            return this.findAppropriatePlace(root.right, value);
        } else {
            //left
            return this.findAppropriatePlace(root.left, value);

        }
    }
}

const test = new BinaryTree(20);
test.insertNode(10);
test.insertNode(30);
test.insertNode(5);
test.insertNode(12);
test.insertNode(3);
test.insertNode(6);
test.insertNode(11);
test.insertNode(15);
test.insertNode(25);
test.insertNode(40);
console.log(test);
console.log('-------------preOrderTraversal---------');
test.preOrderTraversal(test);
console.log('-------------inOrderTraversal---------');
test.inOrderTraversal(test)
console.log('-------------postOrderTraversal---------');
test.postOrderTraversal(test)
test.removeFromNode(30);
console.log(test)

/*
{
    "value": 20,
    "left": {
        "value": 10,
        "left": {
            "value": 5,
            "left": {
                "value": 3,
                "left": null,
                "right": null
            },
            "right": {
                "value": 6,
                "left": null,
                "right": null
            }
        },
        "right": {
            "value": 12,
            "left": {
                "value": 11,
                "left": null,
                "right": null
            },
            "right": {
                "value": 15,
                "left": null,
                "right": null
            }
        }
    },
    "right": {
        "value": 30,
        "left": {
            "value": 25,
            "left": null,
            "right": null
        },
        "right": {
            "value": 40,
            "left": null,
            "right": null
        }
    }
}

-------------preOrderTraversal---------
20
10
5
3
6
12
11
15
30
25
40
-------------inOrderTraversal---------
3
5
6
10
11
12
15
20
25
30
40
-------------postOrderTraversal---------
3
5
6
10
11
12
15
20
25
30
40
------------------------- **After delete node 30** --------------------
BinaryTree {
  value: 20,
  left: BinaryTree {
    value: 10,
    left: BinaryTree { value: 5, left: [BinaryTree], right: [BinaryTree] },
    right: BinaryTree { value: 12, left: [BinaryTree], right: [BinaryTree] }
  },
  right: null
}


*/


This content originally appeared on DEV Community and was authored by Ashutosh Sarangi