How to use Single Traversal In Javascript

Using Lowest Common Ancestor (LCA)

In this approach, we further optimize by finding both the LCA and the distances from the LCA to both nodes in a single traversal of the binary tree. This reduces the time complexity compared to the previous approaches.

We can further optimize by finding both the LCA and the distances from the LCA to both nodes in a single traversal of the binary tree.
During the traversal, if we find both target nodes, we return their depths to their common ancestor.
If only one node is found, we return its depth and continue the traversal.
Once both nodes are found, we return their depths to their common ancestor and calculate the total distance.

Example: To demonsrtate finding the distance between two nodes of Binary tree using single traversal in JavaScript.

JavaScript

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

// Function to find the distance 
// between two nodes in a binary tree
function findDistance(root, p, q) {
    // Helper function to find the 
    // distance from a node to the target
    function findDepth(node, target, depth) {
        if (!node) return 0;
        if (node.val === target) return depth;
        
        const left = findDepth(node.left, target, depth + 1);
        const right = findDepth(node.right, target, depth + 1);
        
        return left || right;
    }

    // Helper function to find the Lowest 
    // Common Ancestor (LCA) of two nodes
    function findLCA(node, p, q) {
        if (!node || node.val === p || node.val === q) return node;
        
        const left = findLCA(node.left, p, q);
        const right = findLCA(node.right, p, q);
        
        if (left && right) return node;
        return left ? left : right;
    }

    // Find the Lowest Common
    // Ancestor (LCA) of the two nodes
    const lca = findLCA(root, p, q);

    // Calculate the distance 
    // from the LCA to each node
    const distanceP = findDepth(lca, p, 0);
    const distanceQ = findDepth(lca, q, 0);
    
    // Total distance between the nodes
    return distanceP + distanceQ;
}

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


const node1 = 4;
const node2 = 6;

// Find distance between node1 and node2
console.log("Distance between", node1, 
    "and", node2, 
    "using further optimized approach with single traversal is", 
    findDistance(root, node1, node2));

Output:

Distance between 4 and 6 using further optimized approach with single traversal is 4

Time Complexity: O(n)

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 Single Traversal In Javascript

Find Distance Between Two Nodes of a Binary Tree using JavaScript

Similar Reads

Contact Us