Height of special binary tree

Tree Depth-First Search Breadth-First Search Binary Tree

74.6% acceptance

Mar 31, 2026

You are given a root, which is the root of a special binary tree with n nodes. The nodes of the special binary tree are numbered from 1 to n. Suppose the tree has k leaves in the following order: b1 < b2 < ... < bk. The leaves of this tree have a special property! That is, for every leaf bi, the following conditions hold: The right child of bi is bi + 1 if i < k, and b1 otherwise. The left child of bi is bi - 1 if i > 1, and bk otherwise. Return the height of the given tree. Note: The height of a binary tree is the length of the longest path from the root to any other node.

Solution

C++

Time O(1)

Space O(1)

LeetCode

solution.cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  int heightOfTree(TreeNode* root) {
    if (!root) return -1;
    // A leaf node is one where its children point to other leaves (circular links)
    // Detect leaf: left child's right == root or right child's left == root
    // Simpler: a leaf is a node whose left and right children are at the same depth or point back up
    // Actually: leaves have circular links. A node is a leaf if its left->right == node (for non-first leaf)
    // Safest: BFS level by level, a node is a leaf if its children point to nodes already seen
    // Simpler approach: a node is a leaf if left child's right pointer points back to it
    if (root->left && root->left->right == root) return 0;
    if (root->right && root->right->left == root) return 0;
    
    int lh = heightOfTree(root->left);
    int rh = heightOfTree(root->right);
    return 1 + max(lh, rh);
  }
};