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