## Wednesday, August 17, 2016

### Find height of a special binary tree whose leaf nodes are connected - GeeksforGeeks

Find height of a special binary tree whose leaf nodes are connected - GeeksforGeeks
Given a special binary tree whose leaf nodes are connected to form a circular doubly linked list, find its height.

The idea is to follow similar approach as we do for finding height of a normal binary tree. We recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. But left and right child of a leaf node are null for normal binary trees. But, here leaf node is a circular doubly linked list node. So for a node to be a leaf node, we check if node’s left’s right is pointing to the node and its right’s left is also pointing to the node itself.
`bool` `isLeaf(Node* node)`
`{`
`    ``// If given node's left's right is pointing to given node`
`    ``// and its right's left is pointing to the node itself`
`    ``// then it's a leaf`
`    ``return` `node->left && node->left->right == node &&`
`           ``node->right && node->right->left == node;`
`}`

`/* Compute the height of a tree -- the number of`
`Nodes along the longest path from the root node`
`down to the farthest leaf node.*/`
`int` `maxDepth(Node* node)`
`{`
`    ``// if node is NULL, return 0`
`    ``if` `(node == NULL)`
`        ``return` `0;`

`    ``// if node is a leaf node, return 1`
`    ``if` `(isLeaf(node))`
`        ``return` `1;`

`    ``// compute the depth of each subtree and take maximum`
`    ``return` `1 + max(maxDepth(node->left), maxDepth(node->right));`
`}`

Read full article from Find height of a special binary tree whose leaf nodes are connected - GeeksforGeeks