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.

Calculate height binary tree
 

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++

Download   Run Code

Output:

The height of given binary tree is 4

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 






Leave a Reply

avatar
  Subscribe  
Notify of