JSInterview30- Part 4:Finding Maximum Distance Between Nodes in a binary tree

Title image

Introduction:

Binary trees are versatile data structures used in various computer science applications. One common problem when working with binary trees is finding the maximum distance between any two nodes. The maximum distance between nodes in a binary tree is the longest path between any two nodes in the tree. This is a popular question asked in interview rounds of Ola.

In this article, we’ll explore how to solve this problem using JavaScript.

Steps:

1. Define the Binary Tree Node: Before we can find the maximum distance between nodes, we need to define a node structure that represents each node in the tree. Each node will have a value and references to its left and right children.
2. Write the Helper Function: We’ll implement a helper function to calculate the height of the tree and the maximum distance between two nodes passing through the current node.
3. Traverse the Tree: We’ll perform a depth-first traversal of the tree, calculating the maximum distance between nodes for each subtree rooted at the current node.
4. Update the Maximum Distance: As we traverse the tree, we’ll update the maximum distance if we find a longer path between two nodes.
5. Test the Function: Finally, we’ll test our function with different binary trees to ensure it works correctly.

Implementation:

// Define the Binary Tree Node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Helper function to calculate height and maximum distance
function findMaxDistance(root, maxDist) {
  // Base case: if root is null, height is 0 and maximum distance is 0
  if (root === null) {
    return { height: 0, maxDist: 0 };
  }
  
  // Recursively calculate height and maximum distance of left and right subtrees
  let left = findMaxDistance(root.left, maxDist);
  let right = findMaxDistance(root.right, maxDist);
  
  // Update maximum distance
  maxDist[0] = Math.max(maxDist[0], left.height + right.height);
  
  // Return height of current subtree and maximum distance
  return {
    height: Math.max(left.height, right.height) + 1,
    maxDist: Math.max(left.maxDist, right.maxDist)
  };
}

// Function to find the maximum distance between nodes in a binary tree
function maxDistance(root) {
  let maxDist = [0]; // Store the maximum distance as a mutable array
  findMaxDistance(root, maxDist);
  return maxDist[0];
}

// Test the function
// Create a binary tree
let 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);

// Calculate the maximum distance between nodes in the binary tree
console.log("Maximum distance between nodes:", maxDistance(root)); // Output: 3

Code explanation:

Let's go through the provided JavaScript code step by step using the same example mentioned in the code snippet:

Step 1: Define the Binary Tree Node

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

Here, we define a class TreeNode to represent each node in the binary tree. Each node has a value property to store the value of the node, and left and right properties to reference its left and right children, respectively.

Step 2: Write the Helper Function

function findMaxDistance(root, maxDist) {
  if (root === null) {
    return { height: 0, maxDist: 0 };
  }
  
  let left = findMaxDistance(root.left, maxDist);
  let right = findMaxDistance(root.right, maxDist);
  
  maxDist[0] = Math.max(maxDist[0], left.height + right.height);
  
  return {
    height: Math.max(left.height, right.height) + 1,
    maxDist: Math.max(left.maxDist, right.maxDist)
  };
}

The findMaxDistance function is a helper function that calculates both the height and the maximum distance between nodes for a given subtree rooted at the current node. It recursively calculates the height of the left and right subtrees, updates the maximum distance if needed, and returns an object containing the height and maximum distance.

Step 3: Function to Find Maximum Distance

function maxDistance(root) {
  let maxDist = [0];
  findMaxDistance(root, maxDist);
  return maxDist[0];
}

The maxDistance function initializes an array maxDist to store the maximum distance between nodes. It then calls the findMaxDistance function with the root node of the binary tree and the maxDist array. After the calculation, it returns the maximum distance stored in the maxDist array.

Step 4: Test the Function

We create a binary tree with the following structure:

      1
     / \
    2   3
   / \
  4   5

Then, we call the maxDistance function with the root node of the binary tree (root). The output will be the maximum distance between any two nodes in the binary tree, which is 3.

Demo link:- Codepen

This output of findMaxDistance function will help in understanding the flow further:-

"root value" 4
"left height" 0 "right height" 0
"maxDist" [0]

"root value" 5
"left height" 0 "right height" 0
"maxDist" [0]

"root value" 2
"left height" 1 "right height" 1
"maxDist" [2]

"root value" 3
"left height" 0 "right height" 0
"maxDist" [2]

"root value" 1
"left height" 2 "right height" 1
"maxDist" [3]

Conclusion:
In this article, we explored how to find the maximum distance between nodes in a binary tree using JavaScript. We defined the structure of a binary tree node, implemented a helper function to calculate the height and maximum distance, and tested our function with a sample binary tree. Understanding how to find the maximum distance between nodes in a binary tree is essential for various applications, such as optimizing tree-based algorithms and data analysis. That’s it from my end for today. Have a nice day ahead 😄

And if you want to see some funny YouTube shorts on programming, check out my YouTube channel below:

SaurabhNative--Youtube