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.

1

/ \

2 3

/ \ \

4 5 6

/

7

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <stdio.h> #include <stdlib.h> // Utility function to find maximum of two integers int max(int x, int y) { return (x > y) ? x : y; } // Data structure for binary tree node struct Node { int data; struct Node *left, *right; }; // Utility function to allocate memory for a binary tree node struct Node* allocateNode(int data) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; node->left = node->right = NULL; return node; } // Recursive function to calculate height of a binary tree with // leaf nodes forming a circular doubly linked list int height(struct Node* node) { // base case: if node is NULL if (node == NULL) return 0; // node is a leaf if its left's right and its right's left // are pointing to the node itself if ((node->left && node->left->right == node) && (node->right && node->right->left == node)) return 1; // recurse for left and right subtree and consider maximum depth return 1 + max(height(node->left), height(node->right)); } // main function int main(void) { struct Node* root = NULL; // construct the tree root = allocateNode(1); root->left = allocateNode(2); root->right = allocateNode(3); root->left->left = allocateNode(4); root->left->right = allocateNode(5); // leaf node root->right->right = allocateNode(6); // leaf node root->left->left->left = allocateNode(7); // leaf node // construct circular doubly linked list from leaves struct Node *L1 = root->left->left->left; struct Node *L2 = root->left->right; struct Node *L3 = root->right->right; // set previous and next pointers of the linked list // (left and right pointer of binary tree node respectively) L1->left = L3; L1->right = L2; L2->left = L1; L2->right = L3; L3->left = L2; L3->right = L1; printf("The height of given binary tree is %d", height(root)); return 0; } |

`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