We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Height of Special Binary Tree

Number: 2944

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given the root of a special binary tree with n nodes where the leaves (in left‐to‐right order b1, b2, …, bk) have the extra property that each leaf’s right child points to the next leaf (or b1 if at the end) and each leaf’s left child points to the previous leaf (or bk if at the beginning), return the height of the tree. Here the height is defined as the number of edges in the longest path from the root to any node.

Key Insights

  • Although leaves have extra pointers to adjacent leaves forming a cycle, every node in the graph is already present in the original tree.
  • The extra leaf connections never allow you to “grow” beyond the maximum tree depth: if a leaf in one branch connects to a leaf in another branch, the tree path to that leaf is already optimal.
  • Therefore, the answer is simply the maximum depth (in terms of edges) of the original tree.
  • A simple depth-first traversal (or breadth-first search) that computes the maximum depth of the tree is sufficient.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes (each node is visited once).
Space Complexity: O(h) where h is the tree height (the maximum recursion stack for DFS or queue size in BFS).

Solution

We solve the problem by performing a DFS (depth-first search) to compute the maximum number of edges from the root to any node. Since the extra pointers among leaves only connect leaves (which already have a computed depth) and would only add one extra edge, they do not affect the maximum depth found by the tree structure. Therefore, our algorithm simply ignores those extra pointers and computes the classic tree height.

The algorithm uses recursion to find the maximum of the left and right subtree heights and adds one for each edge. Special care is taken in the base case so that a single-node tree has height 0.

Code Solutions

# 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

# Function to compute the height of the special binary tree.
def heightOfSpecialBinaryTree(root):
    # Base case: if current node is None, then return -1 because
    # for a single node, height should be 0 (0 edges).
    if root is None:
        return -1
    # Recursively compute the height of left and right subtrees.
    left_height = heightOfSpecialBinaryTree(root.left)
    right_height = heightOfSpecialBinaryTree(root.right)
    # The height at the current node is 1 edge plus the maximum of subtrees' heights.
    return 1 + max(left_height, right_height)

# Example usage:
# Construct the binary tree as per the problem and call heightOfSpecialBinaryTree(root).
← Back to All Questions