How to find the number of height balanced nodes in a tree in O(n) time ?

Question

A node is height balanced if difference between height of left subtree and right subtree is either -1 , 0 or 1 , so how to count such nodes , without maintaining any extra field in the node except for left and right child pointers .

Answer 1

Do a post order traversal of the tree.

First we traverse the left subtree - let it return the height of it - say n1.

Traverse the right subtree - let it return its height - say n2.

Now, if |n1 - n2| <= 1 increment a global counter.

Tree traversal is $O(n)$ and so we are done.