CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to find the nodes which are at the maximum distance in a Binary Tree.ExplanationIn 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
SolutionPython#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 ) JAVAimport 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 arr.add(treeArray[i]); arr.add(treeArray[j]); } //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray else if(distance == maxDistance) { arr.add(treeArray[i]); arr.add(treeArray[j]); } } } //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 arr.Add(treeArray[i]); arr.Add(treeArray[j]); } //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray else if(distance == maxDistance) { arr.Add(treeArray[i]); arr.Add(treeArray[j]); } } } //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
