Problem

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.

Examples

Example 1:

1
2
3
4

Input: root = [1,2,3,null,null,4,5]
Output: 2
Explanation: The given tree is shown in the following picture. Each leaf's left child is the leaf to its left (shown with the blue edges). Each leaf's right child is the leaf to its right (shown with the red edges). We can see that the graph has a height of 2.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2700-2799/2773.Height%20of%20Special%20Binary%20Tree/images/1.png)

Example 2:

1
2
3
4

Input: root = [1,2]
Output: 1
Explanation: The given tree is shown in the following picture. There is only one leaf, so it doesn't have any left or right child. We can see that the graph has a height of 1.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2700-2799/2773.Height%20of%20Special%20Binary%20Tree/images/2.png)

Example 3:

1
2
3
4

Input: root = [1,2,3,null,null,4,null,5,6]
Output: 3
Explanation: The given tree is shown in the following picture. Each leaf's left child is the leaf to its left (shown with the blue edges). Each leaf's right child is the leaf to its right (shown with the red edges). We can see that the graph has a height of 3.
![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2700-2799/2773.Height%20of%20Special%20Binary%20Tree/images/3.png)

Constraints:

  • n == number of nodes in the tree
  • 2 <= n <= 10^4
  • 1 <= node.val <= n
  • The input is generated such that each node.val is unique.

Solution

Method 1 – Depth-First Search (DFS) for Height

Intuition

The special property of the leaves does not affect the height, since the height is defined as the longest path from the root to any node, and the extra leaf connections do not create longer paths. So, we can compute the height using a standard DFS.

Approach

  1. Traverse the tree using DFS.
  2. For each node, recursively compute the height of its left and right subtrees.
  3. The height of the node is 1 plus the maximum of its left and right subtree heights.
  4. Return the height of the root.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    int heightOfTree(TreeNode* root) {
        if (!root) return -1;
        int l = heightOfTree(root->left);
        int r = heightOfTree(root->right);
        return 1 + max(l, r);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}
func heightOfTree(root *TreeNode) int {
    if root == nil {
        return -1
    }
    l := heightOfTree(root.Left)
    r := heightOfTree(root.Right)
    if l > r {
        return l + 1
    }
    return r + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public int heightOfTree(TreeNode root) {
        if (root == null) return -1;
        int l = heightOfTree(root.left);
        int r = heightOfTree(root.right);
        return 1 + Math.max(l, r);
    }
}
1
2
3
4
5
6
7
8
9

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    fun heightOfTree(root: TreeNode?): Int {
        if (root == null) return -1
        val l = heightOfTree(root.left)
        val r = heightOfTree(root.right)
        return 1 + maxOf(l, r)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def heightOfTree(self, root: TreeNode) -> int:
        if not root:
            return -1
        l = self.heightOfTree(root.left)
        r = self.heightOfTree(root.right)
        return 1 + max(l, r)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}
impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}
pub struct Solution;
impl Solution {
    pub fn height_of_tree(root: Option<Box<TreeNode>>) -> i32 {
        match root {
            None => -1,
            Some(node) => {
                let l = Solution::height_of_tree(node.left);
                let r = Solution::height_of_tree(node.right);
                1 + l.max(r)
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}
class Solution {
    heightOfTree(root: TreeNode | null): number {
        if (!root) return -1;
        const l = this.heightOfTree(root.left);
        const r = this.heightOfTree(root.right);
        return 1 + Math.max(l, r);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes, since each node is visited once.
  • 🧺 Space complexity: O(h), where h is the height of the tree, due to recursion stack.