Given a special Binary Tree whose leaf nodes are connected to form a circular doubly linked list. Find the height of this special Binary Tree.
Example 1:
Input:
        1
      /   \
     2     3
    /
   4
Output: 3
Ã¢â¬â¹Explanation: There are 3 edges and 4
nodes in spiral tree where leaf nodes
4 and 3 are connected in circular
doubly linked list form. Thus the
height of spiral tree is 3.
Example 2:
Input:
        1
      /   \
     2     3
    / \
   4   5
  /
 6
Output: 4
Your Task:
You don't need to read input or print anything. Your task is to complete the function findTreeHeight() which takes the root of the special Binary Tree as its input and returns the Height of this special Binary Tree.
In a special Binary Tree, the leaf nodes form a circular doubly linked list.
For Example:
      1
     /   \ 
    2    3
   /  \
  4  5
 /  
6 
In the above binary tree, 6, 5 and 3 are leaf nodes and they form a circular doubly linked list. Here, the left pointer of leaf node will act as a previous pointer of circular doubly linked list and its right pointer will act as next pointer of circular doubly linked list.
Expected Time Complexity: O(Height of the Tree).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 10^{4}

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(Height of the Tree).
Expected Auxiliary Space: O(Height of the Tree).

Starter code:
#User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



# Return the height of the given special binary tree

def findTreeHeight(root):

    #code here

Solutions:
def findTreeHeight(root):
	if root is None:
		return 0
	if root.left and root.left.right == root:
		return 1
	l = findTreeHeight(root.left)
	r = findTreeHeight(root.right)
	return 1 + max(l, r)


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


def findTreeHeight(root):
	q = deque()
	q.append(root)
	h = 0
	while q:
		cur_size = len(q)
		while cur_size > 0:
			node = q.popleft()
			cur_size -= 1
			if node.left:
				if node.left.right != node:
					q.append(node.left)
			if node.right:
				if node.right.left != node:
					q.append(node.right)
		h += 1
	return h


def findTreeHeight(root):
	stack = [(root, 1)]
	while stack:
		(node, count) = stack.pop()
		if node == None:
			return count
		if str(node.data)[:7] == 'visited':
			return node.data[7:]
		node.data = 'visited' + str(count)
		stack.append((node.left, count + 1))
	return 'error'


def findTreeHeight(root):
	if root == None:
		return 0
	if root.left == None and root.right == None:
		return 1
	if root.left and root.left.right == root:
		return 1
	ls = findTreeHeight(root.left)
	rs = findTreeHeight(root.right)
	ans = max(ls, rs) + 1
	return ans


def htg(root, level):
	global res
	if root:
		if root.right:
			if root.right.left == root:
				if level > res:
					res = level
			else:
				htg(root.right, level + 1)
		if root.left:
			if root.left.right == root:
				if level > res:
					res = level
			else:
				htg(root.left, level + 1)
		return

def findTreeHeight(root):
	global res
	res = 0
	htg(root, 1)
	return res


def findTreeHeight(root):
	global res
	res = 0

	def recr(node, level):
		global res
		if node.right:
			if node.right.left == node:
				if level > res:
					res = level
			else:
				recr(node.right, level + 1)
		if node.left:
			if node.left.right == node:
				if level > res:
					res = level
			else:
				recr(node.left, level + 1)
	recr(root, 1)
	return res


def findTreeHeight(root):
	if not root:
		return 0
	if root.left and root.left.right == root or (root.right and root.right.left == root):
		return 1
	l = findTreeHeight(root.left)
	r = findTreeHeight(root.right)
	return max(r, l) + 1


def findTreeHeight(root):
	if not root:
		return 0
	elif root.left and root.left.right == root and root.right and (root.right.left == root):
		return 1
	else:
		lheight = findTreeHeight(root.left)
		rheight = findTreeHeight(root.right)
		if lheight > rheight:
			return lheight + 1
		else:
			return rheight + 1


def findTreeHeight(root):
	if not root:
		return 0
	if root.left and root.right:
		if root.left.right == root and root.right.left == root:
			return 1
	return 1 + max(findTreeHeight(root.left), findTreeHeight(root.right))


def findTreeHeight(root):
	if not root:
		return 0
	queue = [(root, 1)]
	seen = {root: True}
	max_ = 1
	while len(queue):
		(top, level) = queue.pop(0)
		max_ = max(level, max_)
		if top.left and top.left not in seen:
			seen[top.left] = True
			queue.append((top.left, level + 1))
		if top.right and top.right not in seen:
			seen[top.right] = True
			queue.append((top.right, level + 1))
	return max_


import collections

class Node:

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

def findTreeHeight(root):
	max_ = 0
	queue = [(root, 1)]
	nodes = collections.defaultdict(lambda : False)
	max_ = 0
	nodes[root] = True
	while len(queue) != 0:
		(curr, level) = queue.pop(0)
		max_ = max(max_, level)
		if curr == None:
			continue
		if curr.left != None and (not nodes[curr.left]):
			nodes[curr.left] = True
			queue.append((curr.left, level + 1))
		if curr.right != None and (not nodes[curr.right]):
			nodes[curr.right] = True
			queue.append((curr.right, level + 1))
	return max_


def findTreeHeight(root):

	def getHeight(root):
		if root == None:
			return 0
		if root.left != None and root.left.right == root:
			return 1
		if root.right != None and root.right.left == root:
			return 1
		if root.left == None and root.right == None:
			return 1
		a = getHeight(root.left)
		b = getHeight(root.right)
		return 1 + max(a, b)
	return getHeight(root)


def findTreeHeight(root):
	if root:
		if root.right and root.right.left:
			if root.right.left.data == root.data:
				return 1
		return max(findTreeHeight(root.left), findTreeHeight(root.right)) + 1
	else:
		return 0


def findTreeHeight(root):
	if root is None:
		return 0
	if isRootNode(root):
		return 1
	return 1 + max(findTreeHeight(root.left), findTreeHeight(root.right))

def isRootNode(node):
	return node.right and node.right.left == node and node.left and (node.left.right == node)


from collections import deque

def findTreeHeight(root):
	q = deque()
	q.append(root)
	height = 0
	visited = {root: 1}
	while q:
		n = len(q)
		for i in range(n):
			t = q.popleft()
			if t.left and (not visited.get(t.left)):
				q.append(t.left)
				visited[t.left] = 1
			if t.right and (not visited.get(t.right)):
				q.append(t.right)
				visited[t.right] = 1
		height += 1
	return height


def findTreeHeight(root):
	q = deque([root])
	lev = 0
	while q:
		n = len(q)
		while n > 0:
			node = q.popleft()
			n -= 1
			if node.left:
				if node.left.right != node:
					q.append(node.left)
			if node.right:
				if node.right.left != node:
					q.append(node.right)
		lev += 1
	return lev


def isleaf(root):
	return root.left and root.left.right == root and root.right and (root.right.left == root)

def findTreeHeight(root):
	if root == None:
		return 0
	if isleaf(root):
		return 1
	lh = findTreeHeight(root.left)
	rh = findTreeHeight(root.right)
	return max(lh, rh) + 1


def findTreeHeight(root):
	q = deque([root])
	height = 0
	visited = set()
	while q:
		for i in range(len(q)):
			curr = q.popleft()
			visited.add(curr)
			if curr.left and curr.left not in visited:
				q.append(curr.left)
				visited.add(curr.left)
			if curr.right and curr.right not in visited:
				q.append(curr.right)
				visited.add(curr.right)
		height += 1
	return height


from collections import deque

def findTreeHeight(root):
	vis = set()
	queue = deque()
	queue.append(root)
	level = 0
	vis.add(root)
	while queue:
		k = len(queue)
		while k > 0:
			node = queue.popleft()
			if node.left is not None and node.left not in vis:
				queue.append(node.left)
				vis.add(node.left)
			if node.right is not None and node.right not in vis:
				queue.append(node.right)
				vis.add(node.right)
			k -= 1
		level += 1
	return level


def findTreeHeight(root):
	if root is None:
		return None
	from collections import deque
	q = deque()
	q.append(root)
	h = 0
	while len(q):
		for i in range(len(q)):
			node = q.popleft()
			if node.left:
				if node.left.right != node:
					q.append(node.left)
			if node.right:
				if node.right.left != node:
					q.append(node.right)
		h += 1
	return h


def findTreeHeight(root):

	def find_height(root):
		if root:
			if (root.left and root.left.right == root) and (root.right and root.right.left == root):
				return 1
			left = find_height(root.left)
			right = find_height(root.right)
			return max(left, right) + 1
		return 0
	return find_height(root)


def isLeaf(node):
	return node.left and node.left.right == node and node.right and (node.right.left == node)

def findTreeHeight(node):
	if node == None:
		return 0
	if isLeaf(node):
		return 1
	return 1 + max(findTreeHeight(node.left), findTreeHeight(node.right))


def findTreeHeight(root):
	height = 0

	def isLeaf(node):
		return node.left and node.left.right == node and node.right and (node.right.left == node)

	def solve(node):
		nonlocal height
		if not node:
			return 0
		if isLeaf(node):
			return 1
		l = solve(node.left)
		r = solve(node.right)
		temp = max(l, r) + 1
		return temp
	return solve(root)


def findTreeHeight(root):
	if root is None:
		return 0
	if Isleaf(root):
		return 1
	lh = findTreeHeight(root.left)
	rh = findTreeHeight(root.right)
	return 1 + max(lh, rh)

def Isleaf(root):
	return root.left and root.left.right == root and root.right and (root.right.left == root)


def isLeaf(root):
	return root.left and root.left.right == root and root.right and (root.right.left == root)

def findTreeHeight(root):
	if root == None:
		return 0
	if isLeaf(root):
		return 1
	return 1 + max(findTreeHeight(root.left), findTreeHeight(root.right))
from collections import deque

class Node:

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

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root

def saveLeafNodes(root, Leaf):
	if not root:
		return
	saveLeafNodes(root.left, Leaf)
	if not root.left and (not root.right):
		Leaf.append(root)
	saveLeafNodes(root.right, Leaf)

def linkLeafNodes(root):
	Leaf = []
	saveLeafNodes(root, Leaf)
	if len(Leaf) <= 1:
		return
	for i in range(0, len(Leaf)):
		if i == 0:
			Leaf[i].right = Leaf[i + 1]
			Leaf[i].left = Leaf[len(Leaf) - 1]
		elif i == len(Leaf) - 1:
			Leaf[i].right = Leaf[0]
			Leaf[i].left = Leaf[i - 1]
		else:
			Leaf[i].right = Leaf[i + 1]
			Leaf[i].left = Leaf[i - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		linkLeafNodes(root)
		ans = findTreeHeight(root)
		print(ans)


from collections import deque

def findTreeHeight(root):
	q = deque()
	q.append(root)
	level = 0
	while q:
		cur_size = len(q)
		while cur_size > 0:
			node = q.popleft()
			cur_size -= 1
			if node.left:
				if node.left.right != node:
					q.append(node.left)
			if node.right:
				if node.right.left != node:
					q.append(node.right)
		level += 1
	return level


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

def is_leaf(node):
	left = node.left
	right = node.right
	if (right and right.left == node) and (left and left.right == node):
		return True
	return False


def findTreeHeight(root):
	if root is None:
		return 0
	if root.right is not None and root.right.left == root:
		return 1
	elif root.left is not None and root.left.right == root:
		return 1
	return 1 + max(findTreeHeight(root.left), findTreeHeight(root.right))


def isLeaf(node):
	if (node and node.left) and node.left.right == node and (node.right and node) and (node.right.left == node):
		return True
	return False

def findTreeHeight(root):
	if root is None:
		return 0
	if isLeaf(root):
		return 1
	return max(findTreeHeight(root.left), findTreeHeight(root.right)) + 1


def recur(root, level, ans):
	if not root:
		return
	if root.left and root.left.right == root and root.right and (root.right.left == root):
		ans[0] = max(ans[0], level)
		return
	recur(root.left, level + 1, ans)
	recur(root.right, level + 1, ans)

def findTreeHeight(root):
	if not root:
		return 0
	ans = [0]
	recur(root, 1, ans)
	return ans[0]


import collections

def findTreeHeight(root):
	que = collections.deque()
	que.append(root)
	que.append(None)
	height = 0
	while que:
		elm = que.popleft()
		if elm is None:
			if que:
				que.append(None)
			height += 1
		elif elm.left:
			pot_left_circular_node = elm.left
			if pot_left_circular_node.right and pot_left_circular_node.right == elm:
				continue
			else:
				que.append(pot_left_circular_node)
		elif elm.right:
			pot_right_circular_node = elm.right
			if pot_right_circular_node.left and pot_right_circular_node.left == elm:
				continue
			else:
				que.append(pot_right_circular_node)
	return height


def getTreeHeight(root):
	height = 0
	if not root:
		return 0
	if root and root.left and (root.left.right == root) and root.right and (root.right.left == root):
		return 1
	a = getTreeHeight(root.left)
	b = getTreeHeight(root.right)
	height = 1 + max(a, b)
	return height

def findTreeHeight(root):
	return getTreeHeight(root)


def findLeafNodes(root, leaves):
	if root is None:
		return
	t = root
	visited = set()
	leaf = None
	while True:
		if t in visited:
			leaf = t
			break
		visited.add(t)
		if t.left is not None:
			t = t.left
		else:
			t = t.right
	leaves.add(leaf)
	t = leaf
	while t.left not in leaves:
		leaves.add(t.left)
		t = t.left

def findHeight(root, leaves):
	if root is None:
		return 0
	if root in leaves:
		return 1
	return 1 + max(findHeight(root.left, leaves), findHeight(root.right, leaves))

def findTreeHeight(root):
	leaves = set()
	findLeafNodes(root, leaves)
	return findHeight(root, leaves)


def findTreeHeight(root):
	ans = 0
	q = [root]
	seen = set()
	seen.add(root)
	while q:
		n = len(q)
		ans += 1
		for _ in range(n):
			x = q.pop(0)
			if x.left and x.left not in seen:
				q.append(x.left)
				seen.add(x.left)
			if x.right and x.right not in seen:
				q.append(x.right)
				seen.add(x.right)
	return ans


def findTreeHeight(root):
	visited = set()
	if root == None:
		return 0
	q = [[root, 1]]
	height = 0
	while len(q) > 0:
		curr = q.pop(0)
		(curr_node, curr_h) = (curr[0], curr[1])
		if curr_node in visited:
			continue
		else:
			height = max(height, curr_h)
			visited.add(curr_node)
			if curr_node.left != None:
				q.append([curr_node.left, curr_h + 1])
			if curr_node.right != None:
				q.append([curr_node.right, curr_h + 1])
	return height


def findTreeHeight(root):

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


from collections import deque

def findTreeHeight(root):
	if root == None:
		return root
	height = findTreeHeight(root)
	return height

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


def findTreeHeight(root):
	h = 0

	def tra(node, h):
		if node:
			if node.left and node.left.right == node and node.right and (node.right.left == node):
				return 1
			return 1 + max(tra(node.left, h + 1), tra(node.right, h + 1))
		else:
			return 1
	return tra(root, h)


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

def isLeaf(node):
	if node.left and node.left.right == node and node.right and (node.right.left == node):
		return True