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

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

• 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.
• When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
• Define another class which has two attribute root and treeArray.
  • Root represents the root node of the tree and initializes it to null.
  • treeArray will store the array representation of the binary tree.
• nodesAtMaxDistance() will find out the nodes which are present at the maximum distance:

• It will calculate the distance between all the nodes present in the binary tree and store it in the variable distance.
• 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.
• If more than one pair of nodes is at maxDistance then, store them in the array arr.

a. calculateSize() will count the number of nodes present in the tree.

b. convertBTtoArray() will convert the binary tree to its array representation by traversing the tree and adding elements to treeArray.

c. getDistance() will calculate the distance of a given node from the root.

d. LowestCommonAncestor() will find out the lowest common ancestor for the nodes n1 and n2.

• If any of the nodes is equal to the root node, then return root as the lowest common ancestor.
• Else, search nodes n1 and n2 in left subtree and right subtree.
• 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.

a. FindDistance() will calculate the distance between two nodes.

• First, it calculates the distance of each node from the root node.
• Subtract the 2 * distance of lowest common ancestor from this root node

Program:

Output:

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