Height of Special Binary Tree - Solution & Explanation

Q: Is Height of Special Binary Tree easy or hard?

The problem is rated Medium because the traversal itself is straightforward, but recognizing and ignoring the circular leaf connections can be tricky. Once those special pointers are filtered, the remaining logic becomes a standard binary tree height computation.

Q: Height of Special Binary Tree Python/Java solution

Most implementations use a DFS helper function. The function recursively computes left and right subtree heights while ignoring circular leaf links. The same logic works across Python, Java, C++, Go, and TypeScript with time complexity O(n) and recursion space O(h).

Q: How to solve Height of Special Binary Tree in O(n)?

Run a DFS starting from the root and compute subtree heights recursively. Before traversing a child, check whether the pointer is part of the circular leaf connection (node.left.right == node or node.right.left == node). Skip those edges so the traversal follows only real parent-child relationships. This guarantees O(n) time since each node is processed once.

Q: What is the best approach for Height of Special Binary Tree?

Depth-First Search (DFS) is the most common approach. Traverse the tree recursively while ignoring the circular links between leaf nodes by checking if node.left.right == node or node.right.left == node. This visits each node once and computes the height using 1 + max(left, right). The total complexity is O(n) time and O(h) space.

Q: Is Height of Special Binary Tree asked at Google/Amazon/Meta?

Tree traversal and height calculation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that include structural constraints—such as circular leaf links or modified pointers—are common follow-up questions to test deeper understanding of tree traversal logic.

Q: What data structure is used in Height of Special Binary Tree?

The problem uses a binary tree where each node has left and right pointers. The special twist is that leaf nodes are connected in a circular doubly linked list using those same pointers. Solutions typically use recursion with DFS or a queue for BFS to traverse the tree structure safely.

Q: What is the time complexity of Height of Special Binary Tree?

The optimal solution runs in O(n) time because every node in the tree is visited exactly once during traversal. DFS uses O(h) space for the recursion stack where h is the tree height, while a BFS approach uses O(w) space where w is the maximum width of the tree.

MediumPremiumFree on FleetCodeTree Depth-First Search Breadth-First Search Binary Tree10 min read

Practice this problem

Problem Statement

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: b₁<b₂< ... < b_k.

The leaves of this tree have a special property! That is, for every leaf b_i, the following conditions hold:

The right child of b_i is b_{i + 1} if i < k, and b₁ otherwise.
The left child of b_i is b_{i - 1} if i > 1, and b_k 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.

Example 1:

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.

Example 2:

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.

Example 3:

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.

Constraints:

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

Approach Overview

Problem Overview: You are given the root of a special binary tree. In this structure, leaf nodes are connected together in a circular doubly linked list using their left and right pointers. Those links are not real child edges, so they must be ignored while computing the tree height. The task is to return the maximum number of nodes on a path from the root to a valid leaf.

Approach 1: Depth-First Search (DFS) Traversal (O(n) time, O(h) space)

The cleanest solution uses a recursive DFS over the tree. Traverse from the root and compute the height of the left and right subtrees. The tricky part is identifying the fake edges created by the circular leaf list. If node.left exists and node.left.right == node, that pointer belongs to the leaf list and should not be explored. Similarly, if node.right exists and node.right.left == node, it is also part of the leaf linkage. Treat those as null children. After filtering those edges, compute the height using 1 + max(leftHeight, rightHeight). This approach visits each node exactly once, giving O(n) time complexity and O(h) recursion stack space where h is the tree height.

This solution maps directly to standard recursive patterns used in Depth-First Search on a binary tree. The only additional logic is detecting the circular leaf connections before recursing.

Approach 2: Breadth-First Search (Level Order) (O(n) time, O(w) space)

A level-order traversal using a queue also works. Start from the root and process nodes level by level, increasing a height counter after finishing each layer. Before pushing children into the queue, filter out the special leaf links using the same checks: ignore node.left if node.left.right == node and ignore node.right if node.right.left == node. Because each node is enqueued at most once, the traversal runs in O(n) time. The queue can hold up to one level of the tree, giving O(w) space where w is the maximum width.

This approach is easier to visualize because the height naturally corresponds to the number of processed levels. It fits well when you already use Breadth-First Search patterns for tree problems.

Recommended for interviews: The DFS solution is typically expected. It demonstrates that you recognize the circular leaf structure and can safely prune those edges during recursion. Mentioning the BFS alternative shows a solid understanding of traversal strategies, but the recursive DFS version is shorter and easier to implement under interview pressure.

Solution

The key to the problem is how to determine whether a node is a leaf node. We design a function dfs(root, d), where root represents the current node, and d represents the depth of the current node. Each time we search, we update the answer ans = max(ans, d), and then determine whether the current node is a leaf node. If the current node has a left child, and the right child of the left child is not the current node, then we recursively call dfs(root.left, d + 1). If the current node has a right child, and the left child of the right child is not the current node, then we recursively call dfs(root.right, d + 1).

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
DFS Recursive Traversal	O(n)	O(h)	General solution for computing tree height; clean and interview-friendly
BFS Level Order Traversal	O(n)	O(w)	Useful when reasoning about tree levels or when recursion depth may be large

Video Solution

L14. Maximum Depth in Binary Tree | Height of Binary Tree | C++ | Java • take U forward • 383,855 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Height of Special Binary Tree easy or hard?

The problem is rated Medium because the traversal itself is straightforward, but recognizing and ignoring the circular leaf connections can be tricky. Once those special pointers are filtered, the remaining logic becomes a standard binary tree height computation.

Height of Special Binary Tree Python/Java solution

Most implementations use a DFS helper function. The function recursively computes left and right subtree heights while ignoring circular leaf links. The same logic works across Python, Java, C++, Go, and TypeScript with time complexity O(n) and recursion space O(h).

How to solve Height of Special Binary Tree in O(n)?

Run a DFS starting from the root and compute subtree heights recursively. Before traversing a child, check whether the pointer is part of the circular leaf connection (node.left.right == node or node.right.left == node). Skip those edges so the traversal follows only real parent-child relationships. This guarantees O(n) time since each node is processed once.

What is the best approach for Height of Special Binary Tree?

Depth-First Search (DFS) is the most common approach. Traverse the tree recursively while ignoring the circular links between leaf nodes by checking if node.left.right == node or node.right.left == node. This visits each node once and computes the height using 1 + max(left, right). The total complexity is O(n) time and O(h) space.

Is Height of Special Binary Tree asked at Google/Amazon/Meta?

Tree traversal and height calculation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that include structural constraints—such as circular leaf links or modified pointers—are common follow-up questions to test deeper understanding of tree traversal logic.

What data structure is used in Height of Special Binary Tree?

The problem uses a binary tree where each node has left and right pointers. The special twist is that leaf nodes are connected in a circular doubly linked list using those same pointers. Solutions typically use recursion with DFS or a queue for BFS to traverse the tree structure safely.

What is the time complexity of Height of Special Binary Tree?

The optimal solution runs in O(n) time because every node in the tree is visited exactly once during traversal. DFS uses O(h) space for the recursion stack where h is the tree height, while a BFS approach uses O(w) space where w is the maximum width of the tree.

Ready to solve this problem?

Practice Height of Special Binary Tree with our built-in code editor and test cases.

Practice on FleetCode

Binary Tree Inorder Traversal

Unique Binary Search Trees II

Problem Info

DifficultyMedium

Acceptance74.6%

Approaches1

Reading time10 min