# Calculate height of a binary tree with leaf nodes forming a circular doubly linked list

Write an algorithm to compute the height of a binary tree with leaf nodes forming a circular doubly linked list where the left and right pointers of the leaf node will act as a previous and next pointer of circular doubly linked list respectively.

For example, consider below binary tree. The leaf nodes are 7, 5 and 6 which are connected with each other using left and right pointers and forms a circular doubly linked list.

We know that the height of a binary tree is number of nodes present on the longest path from root to leaf node. The idea is to traverse the tree in post-order fashion and calculate the height of left and right subtree. The height of the subtree rooted at any node will be equal to maximum height of its left and right subtree plus one. We recursively apply this property to all tree nodes in bottom-up manner (post-order fashion) and return maximum height of the subtree rooted at that node.

For a normal binary trees, the left and right child of a leaf node are null pointers. But here the left and right child of leaf nodes are acting as previous and next pointer of circular doubly linked list. So in order for a node to be a leaf node, we check if its left’s right and its right’s left are pointing to the node itself.

## C++

Output:

The height of given binary tree is 4

(1 votes, average: 5.00 out of 5)