# Maximum distance nodes of a Binary Tree

Write a program to find the nodes which are at the maximum distance in a Binary Tree.

#### Solution

``````using System;
using System.Collections.Generic;

namespace Pattern
{
class Program
{
public static void Main()
{
var binaryTree = new BinaryTree<int>();
binaryTree.Root = new Node<int>(10);
binaryTree.Root.Left = new Node<int>(20);
binaryTree.Root.Right = new Node<int>(30);
binaryTree.Root.Left.Left = new Node<int>(40);
binaryTree.Root.Left.Right = new Node<int>(50);
binaryTree.Root.Right.Left = new Node<int>(60);
binaryTree.Root.Right.Right = new Node<int>(70);
binaryTree.Root.Right.Right.Left = new Node<int>(100);
binaryTree.Root.Right.Right.Right = new Node<int>(80);
binaryTree.Root.Right.Right.Right.Left = new Node<int>(90);

binaryTree.NodesAtMaxDistance(binaryTree.Root);
}
}

public class BinaryTree<T>
{
public Node<T> Root;
T[] _arr;
int _index;
public BinaryTree()
{
Root = null;
}

int CalculateSize(Node<T> node)
{
if (node == null)
return 0;

return CalculateSize(node.Left) + CalculateSize(node.Right) + 1;
}

public void ConvertToArray(Node<T> node)
{
if (Root == null)
{
Console.WriteLine("Tree is empty");
return;
}

if (node.Left != null)
ConvertToArray(node.Left);

_arr[_index] = node.Data;
_index++;
if (node.Right != null)
ConvertToArray(node.Right);
}

public int GetDistance(Node<T> node, T data)
{
if (node == null) return 0;
var x = 0;
if (node.Data.Equals(data) || (x = GetDistance(node.Left, data)) > 0
|| (x = GetDistance(node.Right, data)) > 0)
{
return x + 1;
}
return 0;
}

public Node<T> LowestCommonAncestor(Node<T> temp, T data1, T data2)
{
if (temp == null) return null;

if (temp.Data.Equals(data1) || temp.Data.Equals(data2))
{
return temp;
}
var left = LowestCommonAncestor(temp.Left, data1, data2);
var right = LowestCommonAncestor(temp.Right, data1, data2);

if (left != null && right != null)
return temp;

if (left != null)
return left;

if (right != null)
return right;

return null;
}

public int FindDistance(T node1, T node2)
{
var d1 = GetDistance(Root, node1) - 1;
var d2 = GetDistance(Root, node2) - 1;

var ancestor = LowestCommonAncestor(Root, node1, node2);
var d3 = GetDistance(Root, ancestor.Data) - 1;
return d1 + d2 - 2 * d3;
}

public void NodesAtMaxDistance(Node<T> node)
{
var maxDistance = 0;
var arr = new List<object>();

var treeSize = CalculateSize(node);
_arr = new T[treeSize];
ConvertToArray(node);

for (var i = 0; i < _arr.Length; i++)
{
for (var j = i; j < _arr.Length; j++)
{
var distance = FindDistance(_arr[i], _arr[j]);
if (distance > maxDistance)
{
maxDistance = distance;
arr.Clear();

}
else if (distance == maxDistance)
{
}
}
}
Console.WriteLine("Nodes which are at maximum distance: ");
for (var i = 0; i < arr.Count; i += 2)
{
Console.WriteLine("( " + arr[i] + "," + arr[i + 1] + " )");
}
}

}

public class Node<T>
{
public T Data;
public Node<T> Left;
public Node<T> Right;

public Node(T data)
{
Data = data;
Left = null;
Right = null;
}
}
}

``````