CareerCup

Here's a dynamic programming solution which does this in O(n).

public int countDepth(int[] tree) {
    int[] height = new int[tree.length];
    for (int i = 0; i < tree.length; i++)
        height[i] = -1;
    int maxHeight = -1;
    for (int i = 0; i < tree.length; i++) {
        if (height[i] == -1)
            maxHeight = max(maxHeight, findHeight(i, height, tree));
    }
}

private int findHeight(int i, int[] height, int[] tree) {
    if (height[i] != -1)
        return height[i];
    if (tree[i] == -1) {
        height[i] = 0;
    else
        height[i] = 1 + findHeight(tree[i], height, tree);
    return height[i];
}

This should work as a simple solution, does anyone have a more effecient one? (call it with -1 for the parent value to start it)

private static int calcDepth(int parent, int[] tree) {		
	int maxDepth = 0;
	for (int i = 0; i < tree.length; i++) {
		if (tree[i] == parent) {
			int depth = 1 + calcDepth(i, tree);
			if (depth > maxDepth) maxDepth = depth;
		}
	}
	return maxDepth;
}

We can do this problem in O(n) time using O(n) space.
1) As each element of the given array(except the root) will be in the range [0,n), so we can create an array of Linked Lists.
2) Now traverse the given array. Insert the index of the element to the respective parent. Also mark out the root in this process. So now the array becomes:

[null,null,4,1->2->3,null]

3) Now create a Queue. Insert the root index into it. And also insert a special symbol say $, to mark the end of the current level. Each time you pop out a element from the queue, push all its children into the queue.
A bit of pseudocode to help.

q.add(rootIndex);
q.add($);
while(!q.isEmpty())
{
	current = q.pop();
	if(current == $ ) // marks the end of current level
	{
		height ++;
		if(!q.isEmpty()) 
			q.add($);
	}
	else
	{
		for each element child in the linked list of the popped element
			q.add(popped element child);
	}
}

Because each node is pushed and popped in the queue at most once, the complexity is O(n).

I think following should work

#include<iostream>
using namespace std;
int arr[]={2,6,3,6,3,6,-1};
int main(){    
    int size=7;
    int cov[size];
    for(int i=0;i<size;i++){
            cov[i]=0;
            cout<<arr[i]<<" "; 
    }
    int l=0;
    for(int i=0;i<size;i++){
        if(arr[i]==-1)continue;
        else {
           cov[arr[i]]=max(cov[arr[i]],cov[i]+1);  
           l=max(l,cov[arr[i]]);
        }
        
    }
    cout<<"\nlength = "<<l+1;
}

#include<stdio.h>
#include<limits.h>
int main()
{
    int tree[50], n, i,cur, h=INT_MIN, t;
    printf("No of nodes: ");
    scanf("%d",&n);
    printf("Elements: ");
    for(i=0; i<n; i++)
        scanf("%d",&tree[i]);
    for(i=0; i<n; i++)
    {
        cur=i;
        t=0;
        while(tree[cur]!=-1)
        {
            cur=tree[cur];
            t++;
        }
        if(t>h)
        h=t;
    }
    printf("\nheight = %d",h);
}

static void GetHeight(int [] a)
        {
            int height=0;
            if ( a != null && a.Length > 0)
            {
                int[] level = new int[a.Length];
                for (int i = 0; i < a.Length; i++)
                {
                    int parentNode = a[i];
                    if (parentNode == -1)
                    {
                        level[i] = 1;
                    }
                    else
                    {
                        if (level[parentNode] == 0)
                        {
                            level[parentNode] = 1;
                        }
                        level[i] = 1 + level[parentNode];
                    }
                    height = Math.Max(height, level[i]);
                }
            }
            Console.WriteLine("Height of tree is : {0}", height);
        }

1. Create an array of n elements, lets call it level[ ]
2. Find the root element index with value -1from node [ ], search(O(n))
3. Set the value of that index in level [ ] to 0
4. Traverse through the node [ ], for each index(lets say index 0), find its parent index value(parent index is 3, index 3's value in level[ ] is 0 and set the value in level[ ] to parent index value (here 0 ) + 1 = 1 This is also O(n)
e.g node[ ] = { 3, 3, 3, 3, -1, 2, 1, 0}
level[ ] = {1, 1, 1, 0, 2, 2, 2}
max value in level [ ] will be the height of the tree. find max is also o(n)

there is simple soln to this by just making the index the element as follows.
h-height
eg-int a[ ]={2,6,3,6,3,6,-1}

int h=0,i=0;
while(i!=-1)
{
i=a[i];
++h;
}
cout>>h;

it gives 4 for the above eg.

{{
class Program
{
static int[] parent = { 3, 4, 3, -1, 2 };
static int[] nodes = { 0, 1, 2, 3, 4 };
static int[] heigths = { 0, 0, 0, 0, 0 };
static int root = -1;
static int max = -1;
static int FindHeigth(int i)
{
var h = heigths[parent[i]];
if (h == 0)
{
return 1 + FindHeigth(parent[i]);
}
else
{
return h + 1;
}
}
static void Main(string[] args)
{
for (var i = 0; i < nodes.Length; i++) {
if (parent[i] == -1) {
heigths[i] = 1;
root = nodes[i];
}
}

for (var i = 0; i < nodes.Length; i++)
{
if (i != root)
{
heigths[i] = FindHeigth(i);
if(max < heigths[i]){
max = heigths[i];
}
}
}

System.Console.WriteLine("Depth " + max);
System.Console.Read();
}
}
}}

#include<unordered_map>
#include<iostream>

using namespace std;

int a[5]={3,3,3,-1,2};
int main()
{
    unordered_map<int ,int> s;
    int i=0,height=-1;
    while(i<5)
    {
        if(s.count(a[i])==0)
        {
            s.insert(pair<int ,int >(i,a[i]));
            height+=1;
        }
        i++;
    }
    cout<<height;
}

javascript solution:

var a=[3,3,3,-1,2,1,0];

var x=[];
var height=0;
for(var i=0; i<a.length; i++) {
    if(a[i]==-1) {
        //do nothing
    } else {
        if(x[a[a[i]]]) { 
            
        } else {
            height++;
            x[a[a[i]]] = 1;
        }
    } 
}

console.debug(height);

Iterative way, use Time O(n) and Space O(n), with C++

#include<iostream>
#include<string.h>
using namespace std;

int GetHeight(int A[], int n){
	if(n <= 1) return 0;
	int height[n];
	memset(height, 0, sizeof(height));
	int v, h, maxH = 0;
	for(int i = 0; i < n; ++i){
		v = A[i]; h = 0;
		while(v >= 0){
			if(height[v] > 0){ h+= (height[v] + 1); break; }
			else ++h;
			v = A[v];
		}
		height[i] = h;
		maxH = max(h, maxH);
	}
	return maxH;
}

int main(){
	int A[] = {3, 3, 3, -1, 2};
	cout << GetHeight(A, sizeof(A)/sizeof(int)) << endl;
	return 0;
}

I have found a nice O(N) time and O(1) space algorithm for this problem (I know its been 4 years but bear with me). A few observations led me to this algorithm:

1. If we idealize and imagine we have O(N) space we can cache the heights of each node we've considered before and for later nodes we can simply go up the tree until we hit a parent in the cache when we instantly know the height and can add all nodes we saw on that path to the cache with their corresponding heights. This is what many people have done in their O(N) time O(N) space solutions. Its clear that this runs in O(N) time as each node in the tree is considered at most twice (except the root).

2. A natural extension to obtain a constant space algorithm would then be to try to use the existing array as a cache. This is exactly what I have achieved. I realized that if we cache the heights directly in the array, we will have no way to tell on successive iterations when to "bail out" and compute the heights from the cached value, as they'd be indistinguishable from other nodes in the array. For example, if we have an array:

[2,0,-1], computing and caching the height of node 0 and its predecessors yields an array that looks like [2,1,-1], but when we consider node 1, it will naively think the value at arr[1] is the predecessor and we will get nonsense output.

Thus, in order for nodes to distinguish between cached values and predecessor values, I cache N+height_of_node. Then, caching works as described in part 1, if I perform comparisons of the predecessor value with N to determine if it is a cached height or not.

Here is the algorithm in C++ (feel free to comment or ask questions):

//This function runs in linear time because each node that is "observed" is set to N+k for some k.
int findTreeHeightFromArray(vector<int> arr) {
	int max_height = 0;
	int N = arr.size();
	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] >= N) {
			//its been marked by a lower node so continue:
			continue;
		}

		int node = i;
		int height = 0;
		while (arr[node] != -1 && arr[node] < N) {
			node = arr[node];
			height++;
		}

		//now go up the tree from i until node and set their values
		int top_height = 0;
		if (arr[node] >= N) {
			top_height = arr[node]-N;
		}

		node = i;
		int tmp_height = N + top_height + height;
		while (arr[node] != -1 && arr[node] < N) {
			int temp = arr[node];
			arr[node] = tmp_height;
			tmp_height--;
			node = temp;
		}
	}

	for (int i = 0; i < arr.size(); i++) {
		if (N - arr[i] > max_height) {
			max_height = arr[i] -N;
		}
	}

	return max_height;
}

Brute force. Space O(1) Time i guess is O(n* m) being m the total depth

#include <iostream>
using namespace std;

// No idea why we cant calculate the size ourself :(, and we need to pass as parameter
int getMaximumDepth(int array[], int arraySize){
    cout<<"getMaximumDepth start \n";

    if(array == NULL){
        return 0;
    }
    
    // int arraySize = sizeof(array)/sizeof(*array);
    cout<<"arraySize" << arraySize << "\n";

    int currentDept;
    int maxDept = 1;
    
    for(int i = 0; i < arraySize; i++) {
        cout<<"i" << i << "\n";
        cout<<"array[" << i << "] = " << array[i] << "\n";
        currentDept = 1;
        int parent = array[i];
        while(parent != -1){
            currentDept ++;
            parent = array[parent];
        }
        
        cout<<"currentDept" << currentDept << "\n";

        if(maxDept < currentDept){
            maxDept = currentDept;
        }
    }
    return maxDept;
}

int main()
{
    int array [] = {3,3,3,-1,2,0,1,2,3,4};
    int arraySize = sizeof(array)/sizeof(*array);

    cout<<"arraySize" << arraySize << "\n";
    cout<<"maxDept:" << getMaximumDepth(array, arraySize) << "\n";
    return 0;
}

The maximum number in the array is the height of the tree ;)
Isn't it ?

It is simply to check number of distinct elements in the array since each distinct element in the array denotes a parent hence introduces a new level. So find out the number of distinct elements in the array. This can be done in O(n) time

create a hash table with <parent,list of children> pairs from the array the number of keys in the array gives the size of the tree.