# Program to Find the Nodes Which are at the Maximum Distance in a Binary Tree

Program to Find the Nodes Which are at the Maximum Distance in a Binary Tree on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

## Q. Program to find the nodes which are at the maximum distance in a Binary Tree.

### Explanation

In this program, we need to find out the nodes which are at the maximum distance in the binary tree. According to our approach, all the distances between all the nodes of the tree will be kept in the variable distance. The distance with the maximum value will be kept by using the variable MaxDistance. Initially, MaxDistance is initialized with the value of distance. If any value is found greater than MaxDistance, overwrite the value of MaxDistance.

Repeat this process until we find the maximum possible distance between two nodes of the tree. The algorithm of the process is given below.

### Algorithm

1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
3. Define another class which has two attribute root and treeArray.
1. Root represents the root node of the tree and initializes it to null.
2. treeArray will store the array representation of the binary tree.
4. nodesAtMaxDistance() will find out the nodes which are present at the maximum distance:
1. It will calculate the distance between all the nodes present in the binary tree and store it in the variable distance.
2. MaxDistance keeps tracks of maximum possible distance between nodes. If maxDistance is less than distance, then the value of distance will be stored in maxDistance. Clears the array to get rid of previously stored values. Nodes which are at the maximum distance will be stored in an array arr.
3. If more than one pair of nodes is at maxDistance then, store them in the array arr.
5. calculateSize() will count the number of nodes present in the tree.
6. convertBTtoArray() will convert the binary tree to its array representation by traversing the tree and adding elements to treeArray.
7. getDistance() will calculate the distance of a given node from the root.
8. LowestCommonAncestor() will find out the lowest common ancestor for the nodes n1 and n2.
1. If any of the nodes is equal to the root node, then return root as the lowest common ancestor.
2. Else, search nodes n1 and n2 in left subtree and right subtree.
3. If a node is found such that n1 is the left child of that node and n2 is right child of that node or vice-versa. Returns that node as the lowest common ancestor.
9. FindDistance() will calculate the distance between two nodes.
1. First, it calculates the distance of each node from the root node.
2. Subtract the 2 * distance of lowest common ancestor from this root node

### Python

```#Represent a node of binary tree
class Node:
def __init__(self,data):
#Assign data to the new node, set left and right children to None
self.data = data;
self.left = None;
self.right = None;

class MaxDistance:
def __init__(self):
#Represent the root of binary tree
self.root = None;
self.treeArray = [];

#convertBTtoArray() will convert binary tree to its array representation
def convertBTtoArray(self, node):
#Check whether tree is empty
if(self.root == None):
print("Tree is empty");
return;
else:
if(node.left != None):
self.convertBTtoArray(node.left);
#Adds nodes of binary tree to treeArray
self.treeArray.append(node.data);
if(node.right != None):
self.convertBTtoArray(node.right);

#getDistance() will find distance between root and a specific node
def getDistance(self, temp, n1):
if (temp != None):
x = 0;
#x will store the count of number of edges between temp and node n1
if (temp.data == n1):
return x + 1;
x = self.getDistance(temp.left, n1);
if(x > 0):
return x + 1;
x = self.getDistance(temp.right, n1);
if(x > 0):
return x + 1;
return 0;
return 0;

#lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
def lowestCommonAncestor(self, temp, n1, n2):
if (temp != None):
#If root is equal to either of node node1 or node2, return root
if (temp.data == n1 or temp.data == n2):
return temp;

#Traverse through left and right subtree
left = self.lowestCommonAncestor(temp.left, n1, n2);
right = self.lowestCommonAncestor(temp.right, n1, n2);

#If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
#Then, return node temp  as lowest common ancestor
if (left != None and right != None):
return temp;

#If nodes node1 and node2 are in left subtree
if (left != None):
return left;

#If nodes node1 and node2 are in right subtree
if (right != None):
return right;

return None;

#findDistance() will find distance between two given nodes
def findDistance(self, node1, node2):
#Calculates distance of first node from root
d1 = self.getDistance(self.root, node1) - 1;
#Calculates distance of second node from root
d2 = self.getDistance(self.root, node2) - 1;

#Calculates lowest common ancestor of both the nodes
ancestor = self.lowestCommonAncestor(self.root, node1, node2);

#If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
d3 = self.getDistance(self.root, ancestor.data) - 1;
return (d1 + d2) - 2 * d3;

#nodesAtMaxDistance() will display the nodes which are at maximum distance
def nodesAtMaxDistance(self, node):
maxDistance = 0;
distance = 0;
arr = [];

#Convert binary tree to its array representation
self.convertBTtoArray(node);

for i in range(0, len(self.treeArray)):
for j in range(i, len(self.treeArray)):
#If distance is greater than maxDistance then, maxDistance will hold the value of distance
distance = self.findDistance(self.treeArray[i], self.treeArray[j]);
if(distance > maxDistance):
maxDistance = distance;
#Clear the arr
arr.clear();
#Add nodes at position i and j to treeArray
arr.append(self.treeArray[i]);
arr.append(self.treeArray[j]);

#If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
elif(distance == maxDistance):
arr.append(self.treeArray[i]);
arr.append(self.treeArray[j]);

#Display all pair of nodes which are at maximum distance
print("Nodes which are at maximum distance: ");
for i in range(0, len(arr), 2):
print("( " + str(arr[i]) + "," + str(arr[i+1]) + " )");

bt = MaxDistance();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.left.right = Node(5);
bt.root.right.left = Node(6);
bt.root.right.right = Node(7);
bt.root.right.right.right = Node(8);
bt.root.right.right.right.left = Node(9);

#Finds out all the pair of nodes which are at maximum distance
bt.nodesAtMaxDistance(bt.root);
```

Output:

```Nodes which are at maximum distance:
( 4,9 )
( 5,9 )
```

### C

```#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

//Represent a node of binary tree
struct node{
int data;
struct node *left;
struct node *right;
};

//Represent the root of binary tree
struct node *root = NULL;

int treeArray[50];
int index = 0;

//createNode() will create a new node
struct node* createNode(int data){
//Create a new node
struct node *newNode = (struct node*)malloc(sizeof(struct node));
//Assign data to newNode, set left and right children to NULL
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

//calculateSize() will calculate size of tree
int calculateSize(struct node *node)
{
int size = 0;
if (node == NULL)
return 0;
else {
size = calculateSize (node->left) + calculateSize (node->right) + 1;
return size;
}
}

//convertBTtoArray() will convert binary tree to its array representation
void convertBTtoArray(struct node *node) {
//Check whether tree is empty
if(root == NULL){
printf("Tree is empty\n");
return;
}
else {
if(node->left != NULL)
convertBTtoArray(node->left);
//Adds nodes of binary tree to treeArray
treeArray[index] = node->data;
index++;
if(node->right != NULL)
convertBTtoArray(node->right);
}
}

//getDistance() will find distance between root and a specific node
int getDistance(struct node *temp, int n1) {
if (temp != NULL) {
int x = 0;
if ((temp->data == n1) || (x = getDistance(temp->left, n1)) > 0
|| (x = getDistance(temp->right, n1)) > 0) {
//x will store the count of number of edges between temp and node n1
return x + 1;
}
return 0;
}
return 0;
}

//lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
struct node* lowestCommonAncestor(struct node *temp, int node1, int node2) {
if (temp != NULL) {
//If root is equal to either of node node1 or node2, return root
if (temp->data == node1 || temp->data == node2) {
return temp;
}

//Traverse through left and right subtree
struct node *left = lowestCommonAncestor(temp->left, node1, node2);
struct node *right = lowestCommonAncestor(temp->right, node1, node2);

//If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
//Then, return node temp  as lowest common ancestor
if (left != NULL && right != NULL) {
return temp;
}

//If nodes node1 and node2 are in left subtree
if (left != NULL) {
return left;
}
//If nodes node1 and node2 are in right subtree
if (right != NULL) {
return right;
}
}
return NULL;
}

//findDistance() will find distance between two given nodes
int findDistance(int node1, int node2) {
//Calculates distance of first node from root
int d1 = getDistance(root, node1) - 1;
//Calculates distance of second node from root
int d2 = getDistance(root, node2) - 1;

//Calculates lowest common ancestor of both the nodes
struct node *ancestor = lowestCommonAncestor(root, node1, node2);

//If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
int d3 = getDistance(root, ancestor->data) - 1;
return (d1 + d2) - 2 * d3;
}

//nodesAtMaxDistance() will display the nodes which are at maximum distance
void nodesAtMaxDistance(struct node *node) {
int maxDistance = 0, distance = 0, counter = 0;
int arr[50];

//Length of treeArray
int treeSize = calculateSize(node);

//Convert binary tree to its array representation
convertBTtoArray(node);

//Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
for(int i = 0; i < treeSize; i++) {
for(int j = i; j < treeSize; j++) {
distance = findDistance(treeArray[i], treeArray[j]);
//If distance is greater than maxDistance then, maxDistance will hold the value of distance
if(distance > maxDistance) {
maxDistance = distance;
//Clear the arr
memset(arr, 0, sizeof(arr));
//Add nodes at position i and j to treeArray
arr[counter++] = treeArray[i];
arr[counter++] = treeArray[j];
}
//If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
else if(distance == maxDistance) {
arr[counter++] = treeArray[i];
arr[counter++] = treeArray[j];
}
}
}
int length = sizeof(arr)/sizeof(arr[0]);
//Display all pair of nodes which are at maximum distance
printf("Nodes which are at maximum distance: ");
for(int i = 0; i < length; i = i + 2) {
if(arr[i] != 0 && arr[i+1] != 0)
printf("\n( %d,%d )", arr[i], arr[i+1]);
}
}

int main()
{
//Add nodes to the binary tree
root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
root->right->right->right = createNode(8);
root->right->right->right->left = createNode(9);

//Finds out all the pair of nodes which are at maximum distance
nodesAtMaxDistance(root);

return 0;
}
```

Output:

```Nodes which are at maximum distance:
( 4,9 )
( 5,9 )
```

### JAVA

```import java.util.ArrayList;

public class MaxDistance {

//Represent a node of binary tree
public static class Node{
int data;
Node left;
Node right;

public Node(int data){
//Assign data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}

//Represent the root of binary tree
public Node root;

int[] treeArray;
int index = 0;

public MaxDistance(){
root = null;
}

//calculateSize() will calculate size of tree
public int calculateSize(Node node)
{
int size = 0;
if (node == null)
return 0;
else {
size = calculateSize (node.left) + calculateSize (node.right) + 1;
return size;
}
}

//convertBTtoArray() will convert binary tree to its array representation
public void convertBTtoArray(Node node) {
//Check whether tree is empty
if(root == null){
System.out.println("Tree is empty");
return;
}
else {
if(node.left != null)
convertBTtoArray(node.left);
//Adds nodes of binary tree to treeArray
treeArray[index] = node.data;
index++;
if(node.right != null)
convertBTtoArray(node.right);
}
}

//getDistance() will find distance between root and a specific node
public int getDistance(Node temp, int n1) {
if (temp != null) {
int x = 0;
if ((temp.data == n1) || (x = getDistance(temp.left, n1)) > 0
|| (x = getDistance(temp.right, n1)) > 0) {
//x will store the count of number of edges between temp and node n1
return x + 1;
}
return 0;
}
return 0;
}

//lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
public Node lowestCommonAncestor(Node temp, int node1, int node2) {
if (temp != null) {
//If root is equal to either of node node1 or node2, return root
if (temp.data == node1 || temp.data == node2) {
return temp;
}

//Traverse through left and right subtree
Node left = lowestCommonAncestor(temp.left, node1, node2);
Node right = lowestCommonAncestor(temp.right, node1, node2);

//If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
//Then, return node temp  as lowest common ancestor
if (left != null && right != null) {
return temp;
}

//If nodes node1 and node2 are in left subtree
if (left != null) {
return left;
}
//If nodes node1 and node2 are in right subtree
if (right != null) {
return right;
}
}
return null;
}

//findDistance() will find distance between two given nodes
public int findDistance(int node1, int node2) {
//Calculates distance of first node from root
int d1 = getDistance(root, node1) - 1;
//Calculates distance of second node from root
int d2 = getDistance(root, node2) - 1;

//Calculates lowest common ancestor of both the nodes
Node ancestor = lowestCommonAncestor(root, node1, node2);

//If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
int d3 = getDistance(root, ancestor.data) - 1;
return (d1 + d2) - 2 * d3;
}

//nodesAtMaxDistance() will display the nodes which are at maximum distance
public void nodesAtMaxDistance(Node node) {
int maxDistance = 0, distance = 0;
ArrayList<Integer> arr = new ArrayList<>();

//Initialize treeArray
int treeSize = calculateSize(node);
treeArray = new int[treeSize];

//Convert binary tree to its array representation
convertBTtoArray(node);

//Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
for(int i = 0; i < treeArray.length; i++) {
for(int j = i; j < treeArray.length; j++) {
distance = findDistance(treeArray[i], treeArray[j]);
//If distance is greater than maxDistance then, maxDistance will hold the value of distance
if(distance > maxDistance) {
maxDistance = distance;
arr.clear();
//Add nodes at position i and j to treeArray
}
//If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
else if(distance == maxDistance) {
}
}
}
//Display all pair of nodes which are at maximum distance
System.out.println("Nodes which are at maximum distance: ");
for(int i = 0; i < arr.size(); i = i + 2) {
System.out.println("( " + arr.get(i) + "," + arr.get(i+1) + " )");
}
}

public static void main(String[] args) {

MaxDistance bt = new MaxDistance();
//Add nodes to the binary tree
bt.root = new Node(1);
bt.root.left = new Node(2);
bt.root.right = new Node(3);
bt.root.left.left = new Node(4);
bt.root.left.right = new Node(5);
bt.root.right.left = new Node(6);
bt.root.right.right = new Node(7);
bt.root.right.right.right = new Node(8);
bt.root.right.right.right.left = new Node(9);

//Finds out all the pair of nodes which are at maximum distance
bt.nodesAtMaxDistance(bt.root);
}
}
```

Output:

```Nodes which are at maximum distance:
( 4,9 )
( 5,9 )
```

### C#

```using System;
using System.Collections;
namespace Tree
{
public class Program
{
//Represent a node of binary tree
public class Node<T>{
public T data;
public Node<T> left;
public Node<T> right;

public Node(T data) {
//Assign data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}

public class MaxDistance<T>{
//Represent the root of binary tree
public Node<T> root;

T[] treeArray;
int index = 0;

public MaxDistance(){
root = null;
}

//calculateSize() will calculate size of tree
int calculateSize(Node<T> node)
{
int size = 0;
if (node == null)
return 0;
else {
size = calculateSize (node.left) + calculateSize (node.right) + 1;
return size;
}
}

//convertBTtoArray() will convert the given binary tree to its corresponding array representation
public void convertBTtoArray(Node<T> node) {
//Check whether tree is empty
if(root == null){
Console.WriteLine("Tree is empty");
return;
}
else {
if(node.left!= null)
convertBTtoArray(node.left);
//Adds nodes of binary tree to treeArray
treeArray[index] = node.data;
index++;
if(node.right!= null)
convertBTtoArray(node.right);
}
}

//getDistance() will find distance between root and a specific node
public int getDistance(Node<T> temp, T n1) {
if (temp != null) {
int x = 0;
if ((temp.data.Equals(n1)) || (x = getDistance(temp.left, n1)) > 0
|| (x = getDistance(temp.right, n1)) > 0) {
//x will store the count of number of edges between temp and node n1
return x + 1;
}
return 0;
}
return 0;
}

//lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
public Node<T> lowestCommonAncestor(Node<T> temp, T n1, T n2) {
if (temp != null) {
//If root is equal to either of node node1 or node2, return root
if (temp.data.Equals(n1) || temp.data.Equals(n2)) {
return temp;
}
//Traverse through left and right subtree
Node<T> left = lowestCommonAncestor(temp.left, n1, n2);
Node<T> right = lowestCommonAncestor(temp.right, n1, n2);

//If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
//Then, return node temp  as lowest common ancestor
if (left != null && right != null) {
return temp;
}
//If nodes node1 and node2 are in left subtree
if (left != null) {
return left;
}
//If nodes node1 and node2 are in right subtree
if (right != null) {
return right;
}
}
return null;
}

//findDistance() will find distance between two given nodes
public int findDistance(T node1, T node2) {
//Calculates distance of first node from root
int d1 = getDistance(root, node1) - 1;
//Calculates distance of second node from root
int d2 = getDistance(root, node2) - 1;

//Calculates lowest common ancestor of both the nodes
Node<T> ancestor = lowestCommonAncestor(root, node1, node2);

//If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
int d3 = getDistance(root, ancestor.data) - 1;
return (d1 + d2) - 2 * d3;
}

//nodesAtMaxDistance() will display the nodes which are at maximum distance
public void nodesAtMaxDistance(Node<T> node) {
int maxDistance = 0, distance = 0;
ArrayList arr = new ArrayList();

//Initialize treeArray
int treeSize = calculateSize(node);
treeArray = new T[treeSize];

//Convert binary tree to its array representation
convertBTtoArray(node);

//Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
for(int i = 0; i < treeArray.Length; i++) {
for(int j = i; j < treeArray.Length; j++) {
distance = findDistance(treeArray[i], treeArray[j]);
//If distance is greater than maxDistance then, maxDistance will hold the value of distance
if(distance > maxDistance) {
maxDistance = distance;
arr.Clear();
//Add nodes at position i and j to treeArray
}
//If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
else if(distance == maxDistance) {
}
}
}
//Display all pair of nodes which are at maximum distance
Console.WriteLine("Nodes which are at maximum distance: ");
for(int i = 0; i < arr.Count; i = i + 2) {
Console.WriteLine("( " + arr[i] + "," + arr[i+1] + " )");
}
}
}

public static void Main()
{
MaxDistance<int> bt = new MaxDistance<int>();
//Add nodes to the binary tree
bt.root = new Node<int>(1);
bt.root.left = new Node<int>(2);
bt.root.right = new Node<int>(3);
bt.root.left.left = new Node<int>(4);
bt.root.left.right = new Node<int>(5);
bt.root.right.left = new Node<int>(6);
bt.root.right.right = new Node<int>(7);
bt.root.right.right.right = new Node<int>(8);
bt.root.right.right.right.left = new Node<int>(9);

//Finds out all the pair of nodes which are at maximum distance
bt.nodesAtMaxDistance(bt.root);
}
}
}
```

Output:

```Nodes which are at maximum distance:
( 4,9 )
( 5,9 )
```

### PHP

```<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
public \$data;
public \$left;
public \$right;

function __construct(\$data){
//Assign data to the new node, set left and right children to NULL
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class MaxDistance{
//Represent the root of binary tree
public \$root;
public \$treeArray;
function __construct(){
\$this->root = NULL;
\$this->treeArray = array();
}

//convertBTtoArray() will convert binary tree to its array representation
function convertBTtoArray(\$node) {
//Check whether tree is empty
if(\$this->root == NULL){
print("Tree is empty <br>");
return;
}
else {
if(\$node->left != NULL)
\$this->convertBTtoArray(\$node->left);
//Adds nodes of binary tree to treeArray
array_push(\$this->treeArray, \$node->data);
if(\$node->right != NULL)
\$this->convertBTtoArray(\$node->right);
}
}

//getDistance() will find distance between root and a specific node
function getDistance(\$temp, \$n1){
if (\$temp != NULL) {
\$x = 0;
if ((\$temp->data == \$n1) || (\$x = \$this->getDistance(\$temp->left, \$n1)) > 0
|| (\$x = \$this->getDistance(\$temp->right, \$n1)) > 0) {
//x will store the count of number of edges between temp and node n1
return \$x + 1;
}
return 0;
}
return 0;
}

//lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
function lowestCommonAncestor(\$temp, \$node1, \$node2) {
if (\$temp != NULL) {
//If root is equal to either of node node1 or node2, return root
if (\$temp->data == \$node1 || \$temp->data == \$node2) {
return \$temp;
}

//Traverse through left and right subtree
\$left = \$this->lowestCommonAncestor(\$temp->left, \$node1, \$node2);
\$right = \$this->lowestCommonAncestor(\$temp->right, \$node1, \$node2);

//If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
//Then, return node temp  as lowest common ancestor
if (\$left != NULL && \$right != NULL) {
return \$temp;
}

//If nodes node1 and node2 are in left subtree
if (\$left != NULL) {
return \$left;
}
//If nodes node1 and node2 are in right subtree
if (\$right != NULL) {
return \$right;
}
}
return NULL;
}

//findDistance() will find distance between two given nodes
function findDistance(\$node1, \$node2) {
//Calculates distance of first node from root
\$d1 = \$this->getDistance(\$this->root, \$node1) - 1;
//Calculates distance of second node from root
\$d2 = \$this->getDistance(\$this->root, \$node2) - 1;

//Calculates lowest common ancestor of both the nodes
\$ancestor = \$this->lowestCommonAncestor(\$this->root, \$node1, \$node2);

//If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
\$d3 = \$this->getDistance(\$this->root, \$ancestor->data) - 1;
return (\$d1 + \$d2) - 2 * \$d3;
}

//nodesAtMaxDistance() will display the nodes which are at maximum distance
function nodesAtMaxDistance(\$node) {
\$maxDistance = 0;
\$distance = 0;
\$arr = array();

//Convert binary tree to its array representation
\$this->convertBTtoArray(\$node);

//Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
for(\$i = 0; \$i < count(\$this->treeArray); \$i++) {
for(\$j = \$i; \$j < count(\$this->treeArray); \$j++) {
\$distance = \$this->findDistance(\$this->treeArray[\$i], \$this->treeArray[\$j]);
//If distance is greater than maxDistance then, maxDistance will hold the value of distance
if(\$distance > \$maxDistance) {
\$maxDistance = \$distance;
\$arr = array();
//Add nodes at position i and j to treeArray
array_push(\$arr, \$this->treeArray[\$i]);
array_push(\$arr, \$this->treeArray[\$j]);
}
//If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
else if(\$distance == \$maxDistance) {
array_push(\$arr, \$this->treeArray[\$i]);
array_push(\$arr, \$this->treeArray[\$j]);
}
}
}
//Display all pair of nodes which are at maximum distance
print("Nodes which are at maximum distance: <br>");
for(\$i = 0; \$i < sizeof(\$arr); \$i = \$i + 2) {
print("( " . \$arr[\$i] . "," . \$arr[\$i+1] . " )");
print("<br>");
}
}
}

\$bt = new MaxDistance();
//Add nodes to the binary tree
\$bt->root= new Node(1);
\$bt->root->left = new Node(2);
\$bt->root->right = new Node(3);
\$bt->root->left->left = new Node(4);
\$bt->root->left->right = new Node(5);
\$bt->root->right->left = new Node(6);
\$bt->root->right->right = new Node(7);
\$bt->root->right->right->right = new Node(8);
\$bt->root->right->right->right->left = new Node(9);

//Finds out all the pair of nodes which are at maximum distance
\$bt->nodesAtMaxDistance(\$bt->root);
?>
</body>
</html>
```

Output:

```Nodes which are at maximum distance:
( 4,9 )
( 5,9 )
```

Next TopicPrograms List