How to use Brute Force In Javascript

Using Lowest Common Ancestor (LCA)

In the brute force approach, we traverse the binary tree recursively, calculating the distance from the root to both target nodes. We then sum up these distances to find the total distance between the nodes.

In this approach, for each node in the binary tree, we find the distance to both target nodes.
We start from the root and traverse the tree recursively.
We calculate the distance to both target nodes for each node encountered using depth-first search.
Finally, we sum up the distances from the root to both nodes to get the total distance.

Example: To demonstrate finding the distance between two nodes of a Binary tree using brute force in JavaScript.

JavaScript

class BinaryNode {
    constructor(val)
    {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// Function to find distance between
// two nodes using brute force approach
function findDistanceBruteForce(root, p, q) 
{
    // Function to find distance
    // from root to a given node
    function findDepth(node, target)
     {
        if (!node) return 0;
        if (node.val === target) return 0;
        
        const left = findDepth(node.left, target);
        const right = findDepth(node.right, target);
        
        if (left !== -1) return left + 1;
        if (right !== -1) return right + 1;
        
        return -1;
    }

    const distanceP = findDepth(root, p);
    const distanceQ = findDepth(root, q);
    
    return distanceP + distanceQ;
}

// Construct the binary tree
const root = new BinaryNode(1);
root.left = new BinaryNode(2);
root.right = new BinaryNode(3);
root.left.left = new BinaryNode(4);
root.left.right = new BinaryNode(5);
root.right.right = new BinaryNode(6);

const node1 = 4;
const node2 = 6;

// Find distance between node1 and node2 using brute force approach
console.log("Distance between", node1, 
    "and", node2, "using brute force approach is", 
    findDistanceBruteForce(root, node1, node2));

Output:

Distance between 4 and 6 using brute force approach is 4

Time Complexity: O(n^2)

Space Complexity: O(h)

Find Distance Between Two Nodes of a Binary Tree using JavaScript

In computer science, binary trees are hierarchical data structures that consist of nodes. Each node can have two children at most – one on the left side and one on the right. These structures have a top-to-bottom order. Solving for distance between any two given nodes is a problem often seen with binary trees. We’ll look at different ways to find this distance in JavaScript.

Problem Description: Given a binary tree and two node values, the task is to find the distance between the two nodes.

Consider the following binary tree:

Explanation: To find the distance between nodes 4 and 6, we first locate their common ancestor, which is node 2. From this ancestor, the path to node 4 is of length 1, and the path to node 6 is of length 3. Therefore, the total distance between nodes 4 and 6 is 4.

Output: The distance between nodes 4 and 6 in the binary tree is 4.

There are several approaches to find the distance between two nodes of a Binary tree using JavaScript which are as follows:

Table of Content

Brute Force Approach
Using Lowest Common Ancestor (LCA)
Using Single Traversal

Tags:

#JavaScript-Program #JavaScript #Web Technologies

Using Lowest Common Ancestor (LCA)

How to use Brute Force In Javascript

Find Distance Between Two Nodes of a Binary Tree using JavaScript

Similar Reads