Find the height of the binary tree given that only the nodes on the even levels are considered as the valid leaf nodes.
The height of a binary tree is the number of edges between the tree’s root and its furthest leaf. But what if we bring a twist and change the definition of a leaf node. Let us define a valid leaf node as the node that has no children and is at an even level (considering root node as an odd level node).
Output :Height of tree is 4
Solution : The approach to this problem is slightly different from the normal height finding approach. In the return step, we check if the node is a valid root node or not. If it is valid, return 1, else we return 0. Now in the recursive step- if the left and the right sub-tree both yield 0, the current node yields 0 too, because in that case there is no path from current node to a valid leaf node. But in case at least one of the values returned by the children is non-zero, it means the leaf node on that path is a valid leaf node, and hence that path can contribute to the final result, so we return max of the values returned + 1 for the current node.
# Program to find height of the tree considering
# only even level leaves.
# Helper class that allocates a new node with the
# given data and None left and right pointers.
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def heightOfTreeUtil(root, isEven):
# Base Case
if (not root):
if (not root.left and not root.right):
# left stores the result of left subtree,
# and right stores the result of right subtree
left = heightOfTreeUtil(root.left, not isEven)
right = heightOfTreeUtil(root.right, not isEven)
#If both left and right returns 0, it means
# there is no valid path till leaf node
if (left == 0 and right == 0):
return (1 + max(left, right))
return heightOfTreeUtil(root, False)
# Driver Code
if __name__ == ‘__main__’:
# Let us create binary tree shown
# in above diagram
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.left.right.left = newNode(6)
print(“Height of tree is”,
# This code is contributed by PranchalK
Height of tree is 4
Time Complexity:O(n) where n is number of nodes in given binary tree.