Algorithm to find Nodes having largest distance in Binary tree.

[pawan chopra]

Hi All,

This is a question asked in interview. I have searched allot but could not get the answer for this. I want to write an algorithm to find nodes having largest distance in a binary tree. Can any one help on this?

[Campbell Ritchie]

Please tell us the details of what they wanted. The first thing you ought to have done is ask what they meant by largest distance.

[pawan chopra]

I have a binary tree. Now what I want is I want to write an algorithm which will give longest path between two nodes. As shown below we can say 5/11 and 4 has longest path between each other. I hope these details will help you to understand the problem.

[William Brogden]

I would use the flood fill algorithm being sure to complete all single steps first.

The last pixel to be "colored" will be furthest away.

Bill

[Mike Simmons]

I suggest looking into Floyd-Warshall algorithm, Dijkstra's algorithm, and Johnson's algorithm.

[Embla Tingeling]

pawan chopra wrote:I have a binary tree. Now what I want is I want to write an algorithm which will give longest path between two nodes.

In a binary tree you cannot speak about the longest path between two nodes really because there's just one path between two nodes. So maybe it's a trick question. Or maybe you want to identify the longest path between ANY two nodes in the tree?

Also in your example tree, what are the numbers? There are doubles so they cannot be node identifiers. Do they represent something else like length for example?

[Mike Simmons]

Silly me, I overlooked the "binary tree" part of the problem. That makes this considerably simpler than the algorithms I suggested. Ignore my last post.

uj nossnahoj wrote:In a binary tree you cannot speak about the longest path between two nodes really because there's just one path between two nodes. So maybe it's a trick question. Or maybe you want to identify the longest path between ANY two nodes in the tree?

The latter is certainly how I would interpret the original question at this point.

[Embla Tingeling]

Mike Simmons wrote:The latter is certainly how I would interpret the original question at this point.

Me too: Find the longest distance between any two nodes in a binary tree (and the numbers in the nodes are node identifiers).

In that case I have a suggestion.

First consider a "complete" binary tree. It's a tree where all nodes are present down to a certain depth. Say we have a complete tree of depth 3 and the nodes are numbered from left to right,

1
2 3
4 5 6 7

Here 2 and 3 are children of 1, and 4 and 5 are children of 2, etcetera. Now if we instead write the numbers in binary representation we get,

1
10 11
100 101 110 111

Note how the number of digits in the binary number corresponds to the node's depth in the tree.

Most binary trees won't be complete like this. Some nodes will be missing. Still the nodes in any binary tree can be given the numbers they would have in a complete tree. This enumeration can be done in one recursive traversal.

Now to calculate the distance between two nodes we strip off all equal binary digits from the left. The number of bits in each number now corresponds to the depth from the closest common parent node. These depths uniquely determines the distance between the nodes!

An example. Determine the distance between 100 and 101,

10|0
10|1

Both numbers have depth 1 from the closest parent (meaning they're direct children). The distance is 1+1 = 2.

Next example,

1|00
1|11

Both numbers have depth 2 from the closest parent (meaning they're grandchildren). The distance is 2+2=4

Next example,

10|
10|0

Here one number actually is the parent so its depth is 0. The other one has depth 1 (a child). The distance is 0+1=1.

[pawan chopra]

Thanks to all of you....I am happy to see algorithms for solving this and also I am sad that I will have to study all of them . One thing I would like to ask I have done my engineering in Electronics but now I have been working with Java from last 3 years. Can any one suggest me how can I start and from where I should start learning all these basic things. Algorithms and datastructures . My friends suggested me to learn C language and datastructures and algorithms and all.

[Embla Tingeling]

pawan chopra wrote:Thanks to all of you....I am happy to see algorithms for solving this and also I am sad that I will have to study all of them . One thing I would like to ask I have done my engineering in Electronics but now I have been working with Java from last 3 years. Can any one suggest me how can I start and from where I should start learning all these basic things. Algorithms and datastructures . My friends suggested me to learn C language and datastructures and algorithms and all.

Well, I've presented a specific algorithm for the problem at hand. The other algorithms are more general in nature and requires that you reformulate the problem. Still you need to be able to traverse a binary tree recursively and you need to find a way to represent and manipulate the "binary numbers" used in the solution.

And you don't have to learn C to learn about algorithms & data structures. Java is just fine.

[Embla Tingeling]

Here's a solution based on my suggestion. The "binary numbers" I introduced really are just an encoded form of paths from the root node down to any specific node. So instead I've used a node list to represent those numbers.

The principle is that to calculate the length between two nodes you first find the closest common ancestor to the nodes. The distance between the nodes then is the sum of the distances from each node to the common ancestor.

The algorithm first collects the node lists of all nodes in one recursive traversal of the tree. Then the distance between all node pairs are calculated and stored in a list. This list is then sorted on distance. Finally the list is printed.

import java.util.ArrayList;
import java.util.Collections;

public class LongestPath {
	
	class Node { // tree node
		int id;
		Node left, right;
		Node(int id) {
			this.id = id;
		}
		Node(int id, Node left, Node right) {
			this(id);
			this.left = left; 
			this.right = right;
		}
	}
	
	final Node root; // tree root
	
	class NodeList extends ArrayList<Node> { // list of nodes
		NodeList() {}
		NodeList(NodeList nl) { // copy constructor
			super(nl);
		}
	}
	
	class NodeListList extends ArrayList<NodeList> { // list of node lists
	}
	
	class Distance implements Comparable<Distance> { // distance between two nodes
		int dist;
		Node from, to;
		Distance(int dist, Node from, Node to) {
			this.dist = dist;
			this.from = from; 
			this.to = to;
		}
		public int compareTo(Distance l) { // of Comparable
			return l.dist - dist;
		}
	}
	
	LongestPath() { // constructor
		root = // create test tree
		new Node(
			1,
			new Node(
					2,
					new Node(4),
					new Node(
							5, 
							null, 
							new Node(6)
					)
			),
			new Node(
					3, 
					new Node(7), 
					null
			)	
		);
	}
	
	void traverse(Node n, NodeList nl, NodeListList nll) { // traverse tree recursively
		if (n != null) { // no leaf
			nl.add(n); // add node to current node list
			nll.add(new NodeList(nl)); // save current node list
			traverse(n.left, nl, nll); // left child
			traverse(n.right, nl, nll); // right child
			nl.remove(nl.size()-1); // remove node from current node list
		}
	}
	
	Distance distance(NodeList nlFrom, NodeList nlTo) { // distance between two nodes
		final int L = Math.min(nlFrom.size(), nlTo.size());
		int i=0;
		while (i<L && nlFrom.get(i)==nlTo.get(i)) i++; // skip to closest common ancestor 
		int d = (nlFrom.size() - i) + (nlTo.size() - i); // distance
		Node from = nlFrom.get(nlFrom.size()-1);
		Node to = nlTo.get(nlTo.size()-1);
		return new Distance(d, from, to);
	}
	
	void solve() { // the solution
		NodeListList nll = new NodeListList(); // list of node lists
		traverse(root, new NodeList(), nll); // walk the tree
		ArrayList<Distance> dl = new ArrayList<Distance>(); // list of distances 
		for (int i=0; i<nll.size(); i++) { // calculate distances
			for (int j=i; j<nll.size(); j++) { // between all tree nodes
				dl.add(distance(nll.get(i), nll.get(j))); // add distance to list
			}
		}
		Collections.sort(dl); // sort list of distances
		for (Distance d : dl) { // print result
			System.out.print("distance(");
			System.out.print(d.from.id);
			System.out.print(",");
			System.out.print(d.to.id);
			System.out.print(") = ");
			System.out.print(d.dist);
			System.out.println();
		}
	}
	
	public static void main(String [] args) { // entry point
		LongestPath lp = new LongestPath(); // leave static context
		lp.solve(); // solution
	}

}

[Raghu Devatha]

Thats very good. Cool!

[pawan chopra]

great work!