Horje
Insert a Node in Binary tree using JavaScript

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child. The topmost node is called the root. Nodes can have values or data, and the left child’s value is less than the parent’s value, while the right child’s value is greater.

There are various approaches to inserting a node in a binary tree using JavaScript which are as follows:

Table of Content

Using Recursive Approach

In the recursive approach, we define a recursive function to insert a node into the binary tree. If the current node is null, we create a new node and return it. Otherwise, we recursively traverse the tree to the left or right based on the value of the new node.

Example: This example uses a recursive approach to Insert a Node in a Binary tree.

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

class BinaryTree {
    constructor() {
        this.root = null;
    }

    insertRecursively(value, node = this.root)
    {
        if (!node) {
            return new Node(value);
        }

        if (value < node.value)
         {
            node.left = this
            .insertRecursively(value, node.left);
        } else if (value > node.value) 
        {
            node.right = this
            .insertRecursively(value, node.right);
        }

        return node;
    }
}

// Create a binary tree
const binaryTree = new BinaryTree();
binaryTree.root = binaryTree.
insertRecursively(5);
binaryTree.insertRecursively(3);
binaryTree.insertRecursively(8);
binaryTree.insertRecursively(1);
binaryTree.insertRecursively(4);
binaryTree.insertRecursively(6);

console.log(binaryTree.root.right.left.value);

Output
6

Time complexity: O(h), where h is the height of the binary tree.

Space complexity: O(n)

Using Iterative Approach

Iterative approach uses a loop to traverse the binary tree iteratively. It starts at the root node and compares the value of the new node with the current node. If the new node’s value is less than the current node’s value, it moves to the left child; otherwise, it moves to the right child. This process continues until it reaches a leaf node, where it inserts the new node.

Example: This example uses Iterative approach to Insert a Node in Binary tree.

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

class BinaryTree {
    constructor() {
        this.root = null;
    }

    insertIteratively(value) {
        const newNode = new Node(value);
        if (!this.root) {
            this.root = newNode;
            return;
        }

        let current = this.root;
        while (true) {
            if (value < current.value)
             {
                if (!current.left) 
                {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) 
                {
                    current
                    .right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }
}

// Create a binary tree
const binaryTree = new BinaryTree();
binaryTree.insertIteratively(5);
binaryTree.insertIteratively(3);
binaryTree.insertIteratively(8);
binaryTree.insertIteratively(1);
binaryTree.insertIteratively(4);
binaryTree.insertIteratively(6);
console.log(binaryTree.root.right.left.value);

Output
6

Time complexity: O(h), where h is the height of the binary tree.

Space complexity: O(1) 




Reffered: https://www.geeksforgeeks.org

JavaScript

Related
What is the using Keyword in Typescript ? What is the using Keyword in Typescript ?
XML Namespaces XML Namespaces
How to use npm Scripts as a Build Tool ? How to use npm Scripts as a Build Tool ?
Remove an Item from Array using UnderscoreJS Remove an Item from Array using UnderscoreJS
How to use the drop method in Lodash ? How to use the drop method in Lodash ?

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 18



 

Horje