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);
            Console.ReadLine();
        }
    }

    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();

                        arr.Add(_arr[i]);
                        arr.Add(_arr[j]);
                    }
                    else if (distance == maxDistance)
                    {
                        arr.Add(_arr[i]);
                        arr.Add(_arr[j]);
                    }
                }
            }
            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;
        }
    }
}