Height of a binary tree

Approach:

• To find height of tree check if left node is null, if not null keep preceding to see next left node increasing the height count with each loop.
• Check if left child is there then go to that of it is null then move to right child, keep moving like this

# Python3 code to implement the above approach using morris
# traversal Algorithm
 
 
class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None
 
# Function to find the height of a binary tree using Morris
# Traversal technique
 
 
def findHeight(root):
	height = 0
	current = root
	while current != None:
		if current.left == None:
			# If left subtree is NULL, move to right
			# subtree
			current = current.right
			height += 1 # Increment the height of the tree
		else:
			# Find the inorder predecessor of current node
			pre = current.left
			while pre.right != None and pre.right != current:
				pre = pre.right
 
			if pre.right == None:
				# Make current node the right child of its
				# inorder predecessor
				pre.right = current
				current = current.left
			else:
				# If the right child of the inorder
				# predecessor already points to the current
				# node, then we have traversed the left
				# subtree and its inorder traversal is
				# complete.
				pre.right = None
				current = current.right # Move to the
				# right subtree
	return height
 
 
# Driver Code
if __name__ == '__main__':
	# Create the binary tree
	root = TreeNode(1)
	root.left = TreeNode(2)
	root.right = TreeNode(3)
	root.left.left = TreeNode(4)
	root.left.right = TreeNode(5)
 
	# Calculate the height of the tree using Morris
	# Traversal technique
	print("Height of the binary tree is:", findHeight(root))