LeetCode Problem 2773

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

LeetCode 2773 - Height of Special Binary Tree

Problem Understanding

This problem gives us the root of a special binary tree. At first glance, it looks like a normal binary tree, but there is an unusual property involving the leaf nodes.

Suppose the leaves of the tree, ordered by their node values, are:

$$b_1 < b_2 < \cdots < b_k$$

For every leaf:

• Its left pointer points to the previous leaf in the ordering.
• Its right pointer points to the next leaf in the ordering.
• The first and last leaves wrap around, forming a cycle among all leaves.

This means that although the structure is called a binary tree, the leaf nodes are connected together in a circular fashion. If we blindly perform a normal DFS or BFS, we can revisit leaves indefinitely and enter an infinite loop.

The task is to return the height of the original tree.

Recall that the height of a tree is the length of the longest path from the root to any other node. In a normal tree this is simply the maximum depth.

The key challenge is that the leaf connections create cycles. These extra pointers are not part of the original tree structure and must not contribute to the height calculation.

The constraints tell us:

• There are up to $10^4$ nodes.
• Every node value is unique.
• Node values range from 1 to $n$.

Since $n$ can be as large as 10,000, we need an $O(n)$ solution.

Important edge cases include:

• A tree with only one leaf.
• A tree where the root has a single child.
• Deep skewed trees.
• Trees where following leaf pointers would create cycles and infinite recursion.
• Trees where a leaf's left or right pointer actually points to another leaf instead of being null.

The problem guarantees that the tree satisfies the special leaf-linking property, so we can rely on that structure.

Approaches

Brute Force

A naive idea is to perform a graph traversal from the root while maintaining a visited set to avoid infinite cycles.

Because the leaf nodes form a circular graph, treating every pointer as a regular edge turns the structure into a graph rather than a tree. We could run DFS or BFS, tracking visited nodes, and compute the maximum distance from the root.

This approach works because the visited set prevents infinite loops. However, it is solving a harder graph problem than necessary. The special structure gives us a simpler observation.

Key Insight

In the original tree, every leaf has no children.

The special leaf links are added afterward. Therefore, a node that is a leaf in the original tree can be recognized because both of its children point back to previously visited ancestors or other leaves instead of extending the tree downward.

More importantly:

When traversing downward from a parent, if one of the child pointers points back toward an already visited node, that edge is one of the artificial leaf-cycle connections and should be ignored.

A DFS can therefore compute the height while avoiding revisiting the parent path.

Since the original structure is a tree plus a cycle among leaves, each genuine tree edge is traversed exactly once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Treats structure as a graph and computes maximum distance with visited tracking
Optimal	O(n)	O(h)	DFS ignores cyclic leaf links and computes tree height directly

Here, $h$ is the height of the tree.

Algorithm Walkthrough

Optimal DFS

1. Start a DFS from the root.
2. Pass the parent node into every recursive call. This allows us to identify edges that lead back toward already explored parts of the structure.
3. For the current node, examine its left child.

• If the left child is nil, its contribution is 0.
• If the left child equals the parent, ignore it because it is not part of the downward tree structure.
• Otherwise recursively compute its height.

4. Perform the same process for the right child.
5. If both valid child heights are absent, the current node behaves as a leaf in the original tree and contributes height 0.
6. Otherwise return:

$$1 + \max(\text{leftHeight}, \text{rightHeight})$$ 7. The value returned from the root is the height of the special binary tree.

Why it works

The only cycles in the structure are the artificial connections among leaves. During DFS, every recursive call remembers the node it came from. Any edge that points back toward an already explored direction cannot belong to the original downward tree structure and is ignored.

As a result, the traversal follows exactly the original tree edges and computes the longest root-to-node path. Therefore the returned value is precisely the tree height.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def heightOfTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], parent: Optional[TreeNode]) -> int:
            if node is None:
                return -1

            best = -1

            if node.left is not None and node.left is not parent:
                best = max(best, dfs(node.left, node))

            if node.right is not None and node.right is not parent:
                best = max(best, dfs(node.right, node))

            return best + 1

        return dfs(root, None)

Implementation Explanation

The recursive function dfs(node, parent) computes the height of the subtree rooted at node.

The parent parameter identifies the node from which we arrived. When examining children, any pointer that leads back to the parent is ignored. These back references arise because of the circular leaf connections.

The variable best stores the largest child height found among valid descendants.

If no valid descendants exist, best remains -1, causing the function to return 0. This correctly represents a leaf whose height is zero.

For internal nodes, the function returns one plus the maximum height among its children.

The result of dfs(root, None) is the height of the entire tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func heightOfTree(root *TreeNode) int {
	var dfs func(node, parent *TreeNode) int

	dfs = func(node, parent *TreeNode) int {
		if node == nil {
			return -1
		}

		best := -1

		if node.Left != nil && node.Left != parent {
			h := dfs(node.Left, node)
			if h > best {
				best = h
			}
		}

		if node.Right != nil && node.Right != parent {
			h := dfs(node.Right, node)
			if h > best {
				best = h
			}
		}

		return best + 1
	}

	return dfs(root, nil)
}

Go-Specific Notes

The Go implementation mirrors the Python solution closely.

Instead of Python's nested function, Go uses a recursive function variable declared with var dfs func(...) int.

Pointer comparison is straightforward because tree nodes are represented as pointers. Checking node.Left != parent and node.Right != parent safely identifies edges that should be ignored.

No special overflow handling is needed because the maximum height is at most n - 1, which is far below Go's integer limits.

Worked Examples

Example 1

Input:

        1
       / \
      2   3
         / \
        4   5

Leaves are 2, 4, and 5.

Special links create a cycle among these leaves.

DFS Trace

Node	Parent	Valid Children	Returned Height
2	1	none	0
4	3	none	0
5	3	none	0
3	1	4, 5	1
1	none	2, 3	2

Answer:

2

Example 2

Input:

    1
   /
  2

Only one leaf exists.

DFS Trace

Node	Parent	Valid Children	Returned Height
2	1	none	0
1	none	2	1

Answer:

1

Example 3

Input:

        1
       / \
      2   3
         /
        4
       / \
      5   6

Leaves are 2, 5, and 6.

DFS Trace

Node	Parent	Valid Children	Returned Height
2	1	none	0
5	4	none	0
6	4	none	0
4	3	5, 6	1
3	1	4	2
1	none	2, 3	3

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is processed once
Space	O(h)	Recursion stack stores one path from root to leaf

The DFS visits each node exactly one time. No node is revisited because edges leading back toward the parent are ignored. Therefore the total work is linear in the number of nodes.

The only extra memory comes from recursion. In the worst case of a completely skewed tree, the recursion depth equals the tree height, giving $O(h)$ auxiliary space.

Test Cases

# Example 1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)
assert Solution().heightOfTree(root) == 2  # balanced example

# Example 2
root = TreeNode(1)
root.left = TreeNode(2)
assert Solution().heightOfTree(root) == 1  # single child

# Example 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.left.left = TreeNode(5)
root.right.left.right = TreeNode(6)
assert Solution().heightOfTree(root) == 3  # deeper branch

# Skewed left tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(4)
assert Solution().heightOfTree(root) == 3  # maximum depth on one side

# Skewed right tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
assert Solution().heightOfTree(root) == 2  # right chain

# Smallest valid tree
root = TreeNode(1)
root.left = TreeNode(2)
assert Solution().heightOfTree(root) == 1  # minimum node count

# Perfect tree of height 2
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
assert Solution().heightOfTree(root) == 2  # perfect binary tree

Test Summary

Test	Why
Example 1	Verifies standard balanced structure
Example 2	Verifies single leaf case
Example 3	Verifies deeper subtree handling
Left-skewed tree	Tests worst-case recursion depth
Right-skewed tree	Tests asymmetric structure
Smallest valid tree	Tests minimum constraint
Perfect tree	Tests balanced multi-level tree

Edge Cases

Single Leaf in the Entire Tree

When the tree contains only one leaf, the special leaf-cycle connections do not create additional reachable descendants. A buggy implementation might incorrectly count the leaf's special references as extra levels. The DFS correctly treats the node as a leaf and returns height zero for it.

Completely Skewed Tree

A tree that forms a single chain has height $n-1$. Such inputs stress recursion depth and often expose off-by-one mistakes. Because the algorithm defines leaf height as zero and adds one at every parent, it computes the correct chain length.

Multiple Leaves Connected in a Cycle

The most important corner case occurs when several leaves are linked together. A naive DFS that blindly follows every child pointer can recurse forever around the cycle. By ignoring edges that lead back toward the traversal path, the algorithm only explores genuine tree descendants and avoids infinite loops.

Root with One Subtree Missing

A node may have only a left child or only a right child. Some implementations incorrectly assume both children exist and mishandle missing branches. This solution independently processes each child and naturally handles absent subtrees without special-case code.