Given a parent array arr[] of a binary tree of N nodes. Element at index i in the array arr[] represents the parent of ith node, i.e, arr[i] = parent(i). Find the height of this binary tree.
Note: There will be a node in the array arr[], where arr[i] = -1, which means this node is the root of binary tree.
Example 1:
Input: N = 7
arr = {-1, 0, 0, 1, 1, 3, 5}
Output: 5
Explanation: Tree formed is:
                    0
                   / \
                  1   2
                 / \
                3   4
               /
              5
             /
            6      Height of the tree= 5
Your Task:
You do not need to read input or print anything. Your task is to complete the function findHeight() which takes N and arr[] as input parameters and returns the height of the given binary tree.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ arr[i] ≤ 105

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def findHeight(self, N, arr):

        # code here

Solutions:
class Solution:

	def solve(self, arr, i, dp):
		if arr[i] == -1:
			return 1
		if dp[i] != -1:
			return dp[i]
		return self.solve(arr, arr[i], dp) + 1

	def findHeight(self, N, arr):
		dp = [-1] * N
		ans = 0
		for i in range(N):
			ans = max(ans, self.solve(arr, i, dp))
		return ans


class Solution:

	def findHeight(self, N, arr):
		res = 0
		for i in range(N):
			curr = i
			height = 0
			while curr != -1:
				height += 1
				curr = arr[curr]
			res = max(res, height)
		return res


class Solution:

	def findHeight(self, N, arr):
		ht = 0
		for i in range(N - 1, -1, -1):
			x = arr[i]
			h1 = 1
			while x >= 0:
				h1 += 1
				x = arr[x]
			ht = max(ht, h1)
		return ht


class Node:

	def __init__(self, data):
		self.left = None
		self.data = data
		self.right = None

class Solution:

	def ConstructTree(self, arr, N, dict, root):
		for i in range(N):
			if arr[i] == -1:
				root[0] = dict[i]
			elif dict[arr[i]].left == None:
				dict[arr[i]].left = dict[i]
			else:
				dict[arr[i]].right = dict[i]

	def Height(self, root):
		if root == None:
			return 0
		return max(self.Height(root.left), self.Height(root.right)) + 1

	def findHeight(self, N, arr):
		dict = {}
		for i in range(N):
			dict[i] = Node(i)
		root = [Node(-1)]
		self.ConstructTree(arr, N, dict, root)
		height = self.Height(root[0])
		return height


class Solution:

	def findHeight(self, N, arr):
		maxi = 0
		for i in range(N - 1, -1, -1):
			count = 1
			item = arr[i]
			while item != -1:
				count += 1
				item = arr[item]
			maxi = max(maxi, count)
		return maxi


class Solution:

	def findHeight(self, N, arr):
		ans = 0
		for value in arr:
			temp = 1
			while value != -1:
				temp += 1
				value = arr[value]
			ans = max(ans, temp)
		return ans


from collections import deque

class Solution:

	def findHeight(self, N, arr):
		d1 = {i: [] for i in range(-1, N)}
		for i in range(N):
			d1[arr[i]].append(i)
		(height, q) = (0, deque())
		q.append([-1, 0])
		while q:
			(top, h) = q.popleft()
			height = max(height, h)
			for i in d1[top]:
				q.append([i, h + 1])
		return height

	def findHeight(self, N, arr):
		res = 0
		for i in range(N):
			(curr, height) = (i, 0)
			while curr != -1:
				(height, curr) = (height + 1, arr[curr])
			res = max(res, height)
		return res


class Solution:

	def findHeight(self, n, arr):
		list_ = [0] * n
		for i in range(n):
			fillArr(arr, list_, i)
		return max(list_)

def fillArr(arr, list_, i):
	if list_[i]:
		return
	if arr[i] == -1:
		list_[i] = 1
		return
	if list_[arr[i]] == 0:
		fillArr(arr, list_, arr[i])
	list_[i] = list_[arr[i]] + 1


class Solution:

	def findHeight(self, N, arr):
		result = 1
		for i in range(N):
			result = max(result, self.checkOtherNodes(arr, i))
		return result

	def checkOtherNodes(self, arr, index):
		currIdx = index
		height = 0
		while currIdx >= 0:
			currIdx = arr[currIdx]
			height += 1
		return height

	def findPathRec(self, arr, index, height):
		idxArr = []
		for i in range(N):
			if arr[i] == index:
				idxArr.append(i)
			if len(idxArr) == 2:
				break
		if len(idxArr) == 0:
			return height
		elif len(idxArr) == 1:
			return self.findPathRec(arr, idxArr[0], height + 1)
		else:
			return max(self.findPathRec(arr, idxArr[0], height + 1), self.findPathRec(arr, idxArr[1], height + 1))


class Node:

	def __init__(self, d):
		self.data = d
		self.left = None
		self.right = None

class Solution:

	def h(self, r):
		if r is None:
			return 0
		return max(1 + self.h(r.left), 1 + self.h(r.right))

	def findHeight(self, N, p):
		l = []
		for i in range(N):
			l.append(Node(i))
		for i in range(N):
			if p[i] != -1:
				if l[p[i]].left is None:
					l[p[i]].left = l[i]
				else:
					l[p[i]].right = l[i]
			else:
				g = i
		return self.h(l[g])


from collections import defaultdict, deque

class Solution:

	def findHeight(self, N, arr):
		adj = defaultdict(list)

		def build_tree(arr):
			root_index = 0
			for i in range(N):
				if arr[i] == -1:
					root_index = i
				else:
					adj[arr[i]].append(i)
			return root_index
		queue = deque()
		height = 0
		root_idx = build_tree(arr)
		queue.append(root_idx)
		while queue:
			level = []
			for node in queue:
				for child in adj[node]:
					level.append(child)
			queue = level
			height += 1
		return height


class Solution:

	def findHeight(self, N, arr):
		depth = [0] * N
		height = 0

		def findDepth(idx):
			if arr[idx] == -1:
				return 1
			if depth[idx] != 0:
				return depth[idx]
			return 1 + findDepth(arr[idx])
		for i in range(N):
			depth[i] = findDepth(i)
			height = max(height, depth[i])
		return height
		height = 0
		for value in arr:
			temp = 1
			while value != -1:
				temp += 1
				value = arr[value]
			height = max(height, temp)
		return height


class Solution:

	def findHeight(self, N, arr):

		def height(idx):
			if arr[idx] == -1:
				return 1
			return 1 + height(arr[idx])
		res = 0
		for i in range(len(arr)):
			res = max(res, height(i))
		return res
		height = 0
		for value in arr:
			temp = 1
			while value != -1:
				temp += 1
				value = arr[value]
			height = max(height, temp)
		return height


class Solution:

	def findHeight(self, N, arr):

		def height(idx):
			if arr[idx] == -1:
				return 1
			return 1 + height(arr[idx])
		he = 0
		for i in range(len(arr)):
			he = max(he, height(i))
		return he


class Solution:

	def findHeight(self, N, arr):
		d = {}
		for i in range(N):
			p = arr[i]
			if p in d:
				d[p].append(i)
			else:
				d[p] = [i]

		def height(n):
			if n not in d:
				return 1
			h = 0
			for b in d[n]:
				h = max(h, height(b) + 1)
			return h
		return height(-1) - 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for i in range(N):
			arr[i] = int(arr[i])
		ob = Solution()
		print(ob.findHeight(N, arr))


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def findHeight(self, N, arr):
		root = None
		if len(arr) == 0:
			return root
		i = 0
		l = len(arr)
		hashTable = {}
		while i < l:
			hashTable[i] = Node(i)
			i += 1
		i = 0
		while i < l:
			if arr[i] == -1:
				root = hashTable[i]
				i += 1
				continue
			if hashTable[arr[i]].left == None:
				hashTable[arr[i]].left = hashTable[i]
			else:
				hashTable[arr[i]].right = hashTable[i]
			i += 1
		return self.height(root)

	def height(self, root):
		if not root:
			return 0
		return max(self.height(root.left), self.height(root.right)) + 1


class Solution:

	def findHeight(self, N, arr):

		def h(root):
			if root == None:
				return 0
			l = h(root.left)
			r = h(root.right)
			return max(l, r) + 1
		node = []

		class Node:

			def __init__(self, key):
				self.data = key
				self.left = None
				self.right = None
		for i in range(N):
			node.append(Node(i))
		root = None
		for i in range(N):
			cn = node[i]
			pnv = arr[i]
			if pnv == -1:
				root = cn
				continue
			pn = node[pnv]
			if pn.left == None:
				pn.left = cn
			else:
				pn.right = cn
		return h(root)


class Solution:

	def findHeight(self, N, arr):
		depth = [None for i in range(N)]
		for i in range(N):
			self._depth(arr, depth, i)
		maxDepth = depth[0]
		for i in range(1, N):
			maxDepth = max(maxDepth, depth[i])
		return maxDepth

	def _depth(self, arr, depth, index):
		if depth[index]:
			return depth[index]
		if arr[index] == -1:
			depth[index] = 1
			return 1
		depth[index] = 1 + self._depth(arr, depth, arr[index])
		return depth[index]


class Solution:

	def findHeight(self, N, arr):
		ht = 0
		for val in arr:
			c = 1
			while val != -1:
				c += 1
				val = arr[val]
			ht = max(ht, c)
		return ht


class Solution:

	def findHeight(self, n, arr):
		result = []
		for i in range(n):
			retn = 0
			s = i
			while s != -1:
				s = arr[s]
				retn += 1
			result.append(retn)
		return max(result)


class Solution:

	def find(self, x, arr):
		if arr[x] == -1:
			return 1
		return 1 + self.find(arr[x], arr)

	def findHeight(self, n, a):
		ans = 0
		for i in range(n):
			ans = max(ans, self.find(i, a))
		return ans


class Solution:

	def findHeight(self, N, arr):
		s = []
		for i in range(len(arr)):
			p = arr[i]
			q = i
			count = 0
			while True:
				if arr[i] == -1:
					s.append([q, count])
					break
				count += 1
				i = arr[i]
		max1 = 0
		for i in range(len(s)):
			if s[i][1] > max1:
				max1 = s[i][1]
		return max1 + 1


class Solution:

	def findHeight(self, n, arr):
		max_h = 0
		for i in range(n - 1, -1, -1):
			j = arr[i]
			h = 1
			while not j < 0:
				j = arr[j]
				h += 1
			max_h = max(h, max_h)
		return max_h


class Solution:

	def findHeight(self, N, arr):
		ans = 1
		for i in range(len(arr)):
			curr = i
			anscur = 1
			while arr[curr] != -1:
				anscur += 1
				curr = arr[curr]
			ans = max(ans, anscur)
		return ans


class Solution:

	def findHeight(self, N, arr):
		h = 1
		arr[0] = 1
		for i in range(1, N):
			arr[i] = arr[arr[i]] + 1
			h = max(h, arr[i])
		return h


class Solution:

	def findHeight(self, N, arr):
		dp = [0] * N
		for i in range(N):
			dp[i] = dp[arr[i]] + 1
		return dp[N - 1]


class Solution:

	def findHeight(self, N, arr):
		height = [1]
		for i in range(1, N):
			height.append(height[arr[i]] + 1)
		return height[N - 1]


class Solution:

	def findHeight(self, N, arr):
		visited = [False] * N
		res = 1
		for i in reversed(range(N)):
			if visited[i]:
				continue
			height = 1
			index = i
			while arr[index] != -1:
				visited[i] = True
				height += 1
				index = arr[index]
			res = max(height, res)
		return res


class Solution:

	def findHeight(self, N, arr):
		res = 0
		for i in range(N - 1, -1, -1):
			h = 0
			j = i
			while j >= 0:
				j = arr[j]
				h += 1
			res = max(h, res)
		return res


class Solution:

	def findHeight(self, N, arr):
		ans = 0
		x = arr[N - 1]
		while x != -1:
			ans += 1
			x = arr[x]
		return ans + 1


class Solution:

	def findHeight(self, N, ar):
		maxi = 0
		c = 0
		for i in range(N - 1, -1, -1):
			ans = 1
			j = i
			while ar[j] != -1:
				ans += 1
				ind = ar[j]
				j = ind
			maxi = max(ans, maxi)
		return maxi


class Solution:

	def findHeight(self, N, arr):
		c = 0
		i = arr[N - 1]
		while i != -1:
			i = arr[i]
			c = c + 1
		return c + 1


class Solution:

	def findHeight(self, N, arr):
		daughters = {}
		for (i, parent) in enumerate(arr):
			daughters[parent] = daughters.get(parent, []) + [i]

		def visit(index, depth, accum):
			d = daughters.get(index)
			if d != None:
				for j in d:
					visit(j, depth + 1, accum)
			else:
				accum[0] = max(accum[0], depth)
		accum = [0]
		visit(-1, 0, accum)
		return accum[0]


class Solution:

	def findHeight(self, N, arr):
		d = {}
		d[0] = 1
		maxm = 0
		for i in range(1, N):
			d[i] = d.get(arr[i], 0) + 1
			maxm = max(d[i], maxm)
		return maxm


class Solution:

	def findHeight(self, N, arr):
		i = N - 1
		height = 1
		while arr[i] != -1:
			i = arr[i]
			height += 1
		return height


class Solution:

	def fun(self, map1, curr):
		if curr not in map1:
			return 0
		if len(map1[curr]) == 1:
			return 1 + self.fun(map1, map1[curr][0])
		return 1 + max(self.fun(map1, map1[curr][0]), self.fun(map1, map1[curr][1]))

	def findHeight(self, N, arr):
		map1 = {}
		for i in range(N):
			map1[arr[i]] = map1.get(arr[i], []) + [i]
		return self.fun(map1, -1)


class Solution:

	def findHeight(self, N, arr):
		tree_height = -1
		for i in arr:
			height = 1
			while i != -1:
				i = arr[i]
				height += 1
			tree_height = max(tree_height, height)
		return tree_height


from collections import defaultdict

class Solution:

	def findHeight(self, N, arr):
		graph = defaultdict(list)
		root = None
		for (i, x) in enumerate(arr):
			graph[x].append(i)
			if x == -1:
				root = i

		def dfs(u):
			h = 0
			for v in graph[u]:
				h = max(h, 1 + dfs(v))
			return h
		return 1 + dfs(root)


class Solution:

	def findHeight(self, N, arr):
		count = 0
		return self.findH(N - 1, arr, count)

	def findH(self, i, arr, count):
		if i == -1:
			return count
		return self.findH(arr[i], arr, count=count + 1)


class Solution:

	def findHeight(self, N, arr):
		ct = 1
		x = arr[N - 1]
		while True:
			if x == -1:
				break
			x = arr[x]
			ct += 1
		return ct


class Solution:

	def height(self, arr, x):
		if arr[x] == -1:
			return 1
		return 1 + self.height(arr, arr[x])

	def findHeight(self, N, arr):
		h = 0
		for i in range(N):
			h = max(h, self.height(arr, arr[i]))
		return h


class Solution:

	def findHeight(self, N, arr):
		depth = [0] * N

		def fillDepth(parent):
			if depth[parent] != 0:
				return
			if parent == -1:
				depth[parent] = 1
				return
			if depth[parent] == 0:
				fillDepth(arr[parent])
				depth[parent] = depth[arr[parent]] + 1
		for i in range(N):
			fillDepth(arr[i])
		return max(depth)


class Solution:

	def dfs(self, k, dic):
		(l, r) = (0, 0)
		if k in dic.keys():
			l = self.dfs(dic[k][0], dic)
		if k in dic.keys() and len(dic[k]) > 1:
			r = self.dfs(dic[k][1], dic)
		return 1 + max(l, r)

	def findHeight(self, N, arr):
		h = 1
		i = -1
		ele = arr[N - 1]
		while ele != -1:
			i = ele
			h += 1
			ele = arr[i]
		return h


class Solution:

	def dfs(self, k, dic):
		(l, r) = (0, 0)
		if k in dic.keys():
			l = self.dfs(dic[k][0], dic)
		if k in dic.keys() and len(dic[k]) > 1:
			r = self.dfs(dic[k][1], dic)
		return 1 + max(l, r)

	def findHeight(self, N, arr):
		dic = {}
		for i in range(0, N):
			if arr[i] in dic.keys():
				dic[arr[i]].append(i)
			else:
				dic[arr[i]] = [i]
		return self.dfs(dic[-1][0], dic)


class Solution:

	def solve(self, i, a):
		if i == -1:
			return 1
		return 1 + self.solve(a[i], a)

	def findHeight(self, n, a):
		return self.solve(n - 1, a) - 1


class Solution:

	def findHeight(self, N, arr):
		return self.solve(N - 1, arr)

	def solve(self, ind, arr):
		if arr[ind] == -1:
			return 1
		return 1 + self.solve(arr[ind], arr)


from collections import defaultdict

class Solution:

	def findHeight(self, N, arr):
		m = -float('inf')
		for i in range(N):
			if arr[i] != -1:
				j = i
				c = 0
				while arr[j] != -1:
					c += 1
					j = arr[j]
				m = max(m, c + 1)
		return m


class Solution:

	def findHeight(self, N, arr):
		i = -1
		h = 1
		ele = arr[N - 1]
		while ele != -1:
			i = arr[i]
			h += 1
			ele = arr[i]
		return h


class Solution:

	def findHeight(self, N, arr):
		visited = {}
		for i in range(N):
			visited[i] = False
		(j, ans) = (1, -1)
		while j < N:
			i = N - j
			if not visited[i]:
				count = 0
				while i > 0:
					visited[i] = True
					i = arr[i]
					count += 1
				ans = max(ans, count)
			j += 1
		return ans + 1


class Solution:

	def fillDepth(self, arr, i, depth):
		if depth[i] != 0:
			return
		if arr[i] == -1:
			depth[i] = 1
			return
		if depth[arr[i]] == 0:
			ob.fillDepth(arr, arr[i], depth)
		depth[i] = depth[arr[i]] + 1

	def findHeight(self, N, arr):
		n = len(arr)
		depth = [0 for i in range(n)]
		for i in range(n):
			ob.fillDepth(arr, i, depth)
		ht = depth[0]
		for i in range(1, n):
			ht = max(ht, depth[i])
		return ht


class Solution:

	def findHeight(self, N, arr):
		(i, j) = (N - 1, N - 1)
		(loc, glo) = (0, 0)
		while i >= 0:
			loc = 0
			j = i
			while j > -1:
				loc += 1
				j = arr[j]
			glo = max(glo, loc)
			i -= 1
		return glo


class Solution:

	def findHeight(self, N, arr):
		childs = {}
		for (index, val) in enumerate(arr):
			if childs.get(val, False):
				childs[val].append(index)
			else:
				childs[val] = [index]
		height = 0
		layer = childs[-1]
		while layer != []:
			height = height + 1
			temp = []
			for i in layer:
				if childs.get(i, False):
					temp.extend(childs[i])
			layer = temp
		return height


class Solution:

	def findHeight(self, N, arr):
		heights = [1] * N
		for i in range(1, N):
			heights[i] = heights[arr[i]] + 1
		return max(heights)


class Node:

	def __init__(self, height):
		self.height = height
		self.left = None
		self.right = None

class Solution:

	def findHeight(self, N, arr):
		nodes = []
		c = 0
		for i in range(N):
			if arr[i] == -1:
				nodes.append(Node(1))
				c = 1
			else:
				h = nodes[arr[i]].height + 1
				c = max(h, c)
				new_node = Node(h)
				nodes.append(new_node)
				if nodes[arr[i]].left:
					nodes[arr[i]].right = new_node
				else:
					nodes[arr[i]].left = new_node
		return c


class Solution:

	def findHeight(self, n, a):
		ma = 0
		for i in range(n - 1, -1, -1):
			c = 1
			while a[i] != -1:
				c += 1
				i = a[i]
			if ma < c:
				ma = c
		return ma