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.
Read full article from 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 ofNodes along the longest path from the root nodedown 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
