CareerCup

Check out "w w w.geeksforgeeks.org/diameter-of-a-binary-tree/" for explanation and the solution for this problem.

Note that there is a very good O(n) solution provided, but it doesn't use parent pointers. I am very interested to see, if there is a better solution using the parent pointers though.

I had to look up what diameter of a tree is: length of longest path between two leaves. My solution is in Java and I'm using the original data structure, without building a regular tree structure first.

The general idea is to start at the leaf nodes and traverse the tree towards the root. Each node is annotated with the maximum height and the max diameter for this node. The diameter only gets updated once - when we hit a path that is already annotated and then we skip to the next iteration. If during traversal we hit a node that has a bigger height than our current path, skip to the next iteration.

Asymptotic Running Time:
O(n) to identify leaf nodes
O(n) to traverse tree
-> O(n)

To see that O(n) is true for the tree traversal:
We visit each leaf node once.
Each inner node is visited only once if it is only on one path.
Each inner node that is on more than one path gets visited again only if the path height is higher at that point. If they were to be visited every time (worst-case), the runtime would be O(n log n). But we can safely assume, that on average that won't happen.

{ { {

int diameter(Node[] nodes) {

// Identify leaf nodes
// TODO could be more efficient by marking nodes that have children as:
// not-leaf-node
ArrayList<Node> leafNodes = new ArrayList<Node (Arrays.asList(nodes));
for(Node n: nodes) {
leafNodes.remove(n.parent);
}

// walk leafNodes up to root and set max height/diameter
// we may have to use hashmaps to set vars to nodes instead of assuming
// member vars inside the nodes

int treeDiameter = 0;

for(Node n: leafNodes) {
int height = 1;
boolean disableDiameterUpdate = false;

while(n != null) {
if(!disableDiameterUpdate && n.maxHeight > 0) {
n.diameter = height + n.maxHeight - 1;
if(n.diameter > treeDiameter)
treeDiameter = n.diameter;
disableDiameterUpdate = true;
}

if(n.maxHeight >= height)
break;

n.maxHeight = height;
height++;
n = n.parent;
}
}

return treeDiameter;
}

} } }

Please define what a diameter of a tree is!

I think this solution should work
1.Split the nodes as parent nodes and leaf nodes(can be done in O(n^2) time, worst case) just mark the node if it is reached by moving to parent of another node
2.Create a global variable max_diameter = 0
3.Mark all parent nodes as white, and distance as 0.
4.For each leaf node, start with temp_distance as zero, and as you move up a parent, keep incrementing the temp_distance count
5.If a parent is marked as white, make distance of parent = temp_distance, mark node as black
6.If parent is marked black, temp = distance stored in parent + temp_distance, if temp > max_diameter, make max_diameter = temp, and if temp_distance > parent distance, update parent distance
7.do this for all nodes
8.max_diameter is the value to be returned

I check this for all cases and it worked fine, if someone can come up with a counterexample, please post it here

Java Implementation of tree diameter
/**
6
/ \
2 7
/ \ \
1 4 9
/ \ /
3 5 8
*/

public class TreeDiameter {
	static class CustomInteger{
		int value;
		CustomInteger(int value){
			this.value = value;
		}
	}
	
	public static int treeDiameter(TreeNode root, CustomInteger height){
		CustomInteger leftHeight = new CustomInteger(0), rightHeight = new CustomInteger(0);
		if(root == null){
			height.value = 0;
			return 0;
		}
	  
		/* Get the heights of left and right subtrees in lh and rh 
	       and store the returned values in ldiameter and ldiameter */
		int ldiameter = treeDiameter(root.getLeftNode(), leftHeight);
		int rdiameter = treeDiameter(root.getRightNode(), rightHeight);
	  
		/* Height of current node is max of heights of left and right subtrees plus 1*/
		height.value = Math.max(leftHeight.value, rightHeight.value) + 1;
		
		return Math.max(leftHeight.value + rightHeight.value + 1, Math.max(ldiameter, rdiameter));
	}
	
	public static void main(String[] args) {
		TreeNode root = new TreeNode(6);
		root.setLeftNode(new TreeNode(2));
		root.setRightNode(new TreeNode(7));
		root.getLeftNode().setLeftNode(new TreeNode(1));
		root.getLeftNode().setRightNode(new TreeNode(4));
		root.getLeftNode().getRightNode().setLeftNode(new TreeNode(3));
		root.getLeftNode().getRightNode().setRightNode(new TreeNode(5));
		root.getRightNode().setRightNode(new TreeNode(9));	
		root.getRightNode().getRightNode().setLeftNode(new TreeNode(8));
	
		CustomInteger hgt = new CustomInteger(0);
		System.out.println(treeDiameter(root, hgt));
	}
}

assume that all nodes are stored in an array or a list:

// mark non-leaf nodes
for each node do
  mark its direct parent node
end
// get max length
for each node do
  if node is marked then //non-leaf
    skip
  else // leaf
    visit all parent nodes until root and count the length
    keep the max length
  end
end

the worst case time complexity is O(nlogn)

I think we just know the parent of each node and know nothing about their sons. And the tree can be any tree, not only BST. When allowed to use O(n) space and the space is static, I can give an algorithm with O(nh) time.

(Of course, we can malloc the sons of each node, but the memory will be dynamic.)

Here's the program in C++:

int getDiameter (struct node n[], int num) {
	struct node * tmp;
	int dep[num];
	int ret = 0;
	memset(dep, -1, sizeof(dep));
	for (int i = 0; i < num; ++ i) {
		tmp = &n[i];
		int count = 0;
		while (! tmp) {
			int index = (tmp - n) / sizeof(struct node);

			if (dep[index] == -1) {
				dep[index] = count;
			} else {
				ret = max(ret, count + dep[index]);
				if (dep[index] < count) {
					dep[index] = count;
				} else {
					break;
				}
			}
			tmp = tmp->p;
			++ count;
		}
	}
}

How is the tree represented? I mean, if it is represented by the root of the tree, there is no way to access any other node if only parent nodes are given.

Based on the description of question, here is my assumption:
Tree has three nodes
a) Left Node
b)Right Node
c)Parent Node
Maximum diameter of tree will be distance between two nodes.
These two nodes will be leaf nodes only.
so, here is pseudo code:
1.Find farthest leaf node in left subtree:
Traverse Left subtree and store all leaf nodes in an array .
Loop through all leaf nodes and use parent pointers to find distance to root node, using a temp varaible. Keep updating temp varaible with Max distance.
2. Find farthest leaf node in right subtree
Find all leaf nodes in right subtree of root node.
Traverse till each leaf node and record the maximum distance.
Diameter will be distance between leaf node in left subtree which is farthest from root , and leaf node in right subtree which is farthest from root.

Please comment your views if My analysis is in correct direction or I am missing something.

I suppose this problem could be solved as follows:
1. use the given parent information to build up the topology of the tree. i.e., if a is the parent node of b, add a link between a and b.
2. start with any node u of the tree, use a breadth first search to find the farthest node of u (suppose it's s).
3. start with node s, use a breadth first search to find the farthest node of s (suppose it's t). The distance between s and t would be the required diameter.

For binary tree there is simple answer in O(n).
But in general case, it's the longest path problem in undirected acyclic graph, no simple solution, bounds by theta(n^3) or n^2 depending on implementation.

I think for an O(n) solution we need to cheat a bit.

struct bst {
	int diameter;
	int max_depth;
	int index;
	struct bst *parent;
}

Lets say the nodes are currently represented as struct bst *nodes[n];
find the max value of the index: let that be MAX_INDEX
Traverse through the above array to find that value. O(n);

struct nodes {
	struct bst *child1;
	struct bst *child2;
	
}

Need some memory to create an additional representation.
struct nodes *node_array[MAX_INDEX];

Now browse through *nodes[n] again

for each node in nodes[n]
Find its parent
add the curent node to node_array[parent->index]->child = curr_node;

this can be done in 0(n) time too. Now its the traditional BST problem we can solve in traditional manner

Its kind of cheating but doesnt say we cant do it!

Definition:
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

Algorithm:
The diameter of a tree T is the largest of the following quantities:
* the diameter of T’s subtree (path does not go through the root)
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

Code： (with test case in main)

#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

typedef struct node{
  node* parent;
}Node;

int height( Node* n, vector<Node*> t ){  
  if( is_leaf( n, t ) )
    return 0;
  
  int maxH = 0;
  int size = t.size();
  for(int i = 0; i < size; i++ )
	if( t[i] -> parent == n )
	  maxH = height( t[i], t ) > maxH? height( t[i], t ) : maxH;
  return maxH + 1;     
}

bool single_child(Node* n, vector<Node*> t){
  int size = t.size();
  int cnt = 0;
  for( int i = 0; i < size; i++ )
    if( t[i] -> parent == n ){
      cnt ++;
      if( cnt >= 2 )
	return false;
    }
  if( cnt == 1 )
    return true;
}

int diameter ( Node* n, vector<Node*> t ){
  if( is_leaf( n, t ) ) 
    return 0;
  else if( single_child( n,t ) )
    return 0;
  else{ 
    int size = t.size();
    int maxD = 0;
    for( int i = 0; i < size; i++ ){ // not through n
      if ( t[i] != n && t[i] -> parent == n ){
	int d = diameter( t[i] , t ); 
	maxD = d > maxD? d : maxD;
      }
    }
   
    for( int i = 0; i < size; i++ )  // through n
      if( t[i] -> parent == n )
	for( int j = 0; j < size; j++ )
	  if( j != i && t[j] -> parent == n ){
	    int d = height( t[i], t ) + height( t[j], t ) + 3;
	    maxD = d > maxD? d : maxD;
	  }
 
    return maxD;
  }
}

int main(){
  vector<Node*> t;
  Node* n1 = new Node;
  n1 -> parent = NULL;
  Node* n2 = new Node;
  n2 -> parent = n1;
  Node* n3 = new Node;
  n3 -> parent = n1;
  node* n4 = new Node;
  n4 -> parent = n2;
  node* n5 = new Node;
  n5 -> parent = n2;
  node* n6 = new Node;
  n6 -> parent = n5;
  node* n7 = new Node;
  n7 -> parent = n6;
  
  t.push_back(n1);
  t.push_back(n2);
  t.push_back(n3);
  t.push_back(n4);
  t.push_back(n5);
  t.push_back(n6);
  t.push_back(n7);
  cout << diameter( n1, t ) << endl;
}

find the longest path (travel parent pointer).
set parent pointer to null for this path.
find another longest path.
return add the length - 1

Diameter = Max(depth(leftSubTree), depth(RightSubTree)) + 1;

/* Should work; should be bounded by O(2n) */
public class 
PointerToParent 
{
	public static class
	Node
	{
		Node parent;
		public Node(Node parent) { this.parent = parent; }
	}
	
	public static int
	PP
	(List<Node> ns)
	{
		Map<Node, Integer> hm = new HashMap<>();
		int max_len = 0;
		
		for (Node n : ns) {
			Node cur = n;
			int len = 0;
			while (cur.parent != null && !hm.containsKey(cur)) {
				cur = cur.parent;
				len++;
			}
			if (hm.containsKey(cur)) len += hm.get(cur);
			
			hm.put(n, len);
			if (len > max_len) max_len = len;
			
			cur = n;
			while((cur = cur.parent) != null && !hm.containsKey(cur))
				hm.put(cur, --len);
		}
		
		return max_len;
	}
}

Even if you don't have parent pointer you can solve this problem in O(n).
Use following code

int getDiameter(struct node * root, int *h) {
    if(root == NULL) {
        *h = 0;
        return 0;
    }
    
    int lh = 0;
    int rh = 0;
    int ld = 0;
    int rd = 0
    
    ld = getDiameter(root->l, &lh);
    rd = getDiameter(root->r, &rh);
    
    *h = max(lh, rh) + 1;
    return (max(lh+rh+1, max(ld, rd));
}

if you know bfs algo to find diameter of any tree/graph the below is the answer in O(n). if you don't then google it first.
Algo:
1. find the max height leaf node - o(n);
2. travel that leaf node up to root node and mark each node's parent to null.
3. find the max height leaf node now - O(n)
4 answer is the distance between #1 node and #3 node.

I think this does not work always as in the case of below tree
4
2 7
5 8
9

In this case, the max diameter is 5 but the above program returns 4. Because
1. When you start from node 2, then height(4) = 2. The diameter at node 4 is not calculated yet
2. Now we start from node 5, then height(7)= 2 and node(4) is already annotated so the diameter of node 4 will be calculated as 4
3. Now we start from 9, then node 7 is already annotated so diameter at node 7 will be 4.
4. But the actual diameter is 5
5. Correct me if I am wrong

We have the child-parent relationship available to us. In addition, we know where the parent of the root is (i.e., NULL or -1). Here, I am assuming we know the number of the nodes to be n:

diameter=INT_MIN;
for(i=0;i<n;i++)
{
  cnt=0;
  tmp=node[i];
  while(tmp!=-1) //-1 is equivalent to NULL if pointers are used
  {
     cnt++;
     tmp=parent[tmp];
  }
  if(cnt>diameter)
      diameter=cnt;

}

Why cant just sort both the string and match them.

If there are only parent node . The diameter of the tree would the largest path from the leaves to the root

For example consider the tree

10
	2  		3
4				6
					7

Diameter : Longest path between two nodes

For the example above the longest path would be from 7 to 10 (10 has no child pointers) since all the paths are directed paths from the leaves to root .

Isn't that the height of the tree?