Trees and Binary Search Trees Questions

Idea
The slow part in the original version is recomputing heights for the same subtree many times. I would make one DFS return the height of a subtree, and use -1 as a sentinel meaning unbalanced. That lets me stop early as soon as imbalance is detected.

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left_h = height(node.left)
        if left_h == -1:
            return -1

        right_h = height(node.right)
        if right_h == -1:
            return -1

        if abs(left_h - right_h) > 1:
            return -1

        return max(left_h, right_h) + 1

    return height(root) != -1

Worked example
For a skewed chain 1 -> 2 -> 3 -> 4, the imbalance is detected near the top once the left and right subtree heights differ by more than 1, and the -1 bubbles upward immediately.

Why this is better
Each subtree is processed once, so the runtime becomes O(n) instead of repeatedly revisiting nodes. Space is O(h) for the recursion stack.

To solve this in O(n) time we compute subtree heights bottom-up (post-order) and short-circuit when we detect imbalance. The helper returns -1 to indicate the subtree is unbalanced; otherwise it returns the subtree height. The main function checks the helper's result.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_balanced(root: TreeNode) -> bool:
    """
    Returns True if the binary tree is height-balanced.
    Uses a post-order traversal that returns -1 on imbalance to short-circuit.
    """

    def height(node: TreeNode) -> int:
        if node is None:
            return 0
        lh = height(node.left)
        if lh == -1:
            return -1  # left subtree already unbalanced
        rh = height(node.right)
        if rh == -1:
            return -1  # right subtree already unbalanced
        if abs(lh - rh) > 1:
            return -1  # current node unbalanced
        return 1 + max(lh, rh)

    return height(root) != -1

Key points:

• Uses post-order so each node visited once: O(n) time.
• Space: O(h) recursion stack, where h is tree height (worst-case O(n)).
  Edge cases:
• Empty tree -> balanced.
• Skewed tree -> detected quickly but still O(n).
  Alternative:
• Use iterative post-order with a stack and memoized heights if recursion depth is a concern.

To compute the diameter (number of nodes on the longest path between any two nodes) in O(n) time, compute height and diameter in one DFS: for each node, get left/right heights and diameters, then:

• height = 1 + max(left_height, right_height)
• diameter_through_node = left_height + right_height + 1 (counts nodes)
• diameter = max(left_diameter, right_diameter, diameter_through_node)

This visits each node once.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root):
    """
    Returns diameter (number of nodes on longest path) of binary tree.
    O(n) time, O(h) recursion stack.
    """
    def helper(node):
        # returns (height, diameter)
        if not node:
            return 0, 0  # height=0, diameter=0 for empty subtree
        lh, ld = helper(node.left)
        rh, rd = helper(node.right)
        height = 1 + max(lh, rh)
        dia_through = lh + rh + 1
        diameter = max(ld, rd, dia_through)
        return height, diameter

    _, diameter = helper(root)
    return diameter

Key points:

• Empty tree returns 0.
• Single-node tree: height=1, diameter=1.
• Time: O(n) because each node visited once. Space: O(h) recursion stack.

Example:

• Tree: 1
  /
  2 3
  /
  4 5
  Longest path 4-2-5 (or 4-2-1-3) has 4 nodes -> function returns 4.

To validate a BST in O(n), two common approaches are:

1. Recursive min/max range: pass allowable (low, high) bounds down recursion — each node must satisfy low < node.val < high (or <= depending on duplicate policy).
2. Iterative inorder traversal: a BST's inorder sequence is monotonic increasing (or non-decreasing if duplicates allowed on the right). Use a stack to traverse and compare each visited value with previous.

Recursive implementation (range checks):

# python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_bst_range(root, allow_equal=False):
    """
    allow_equal=False: strict BST (left < node < right)
    allow_equal=True: allow duplicates (left <= node <= right) - typically duplicates go to one side
    """
    def helper(node, low, high):
        if not node:
            return True
        if allow_equal:
            if not (low <= node.val <= high):
                return False
        else:
            if not (low < node.val < high):
                return False
        return helper(node.left, low, node.val if allow_equal else node.val) and \
               helper(node.right, node.val if allow_equal else node.val, high)
    import math
    return helper(root, -math.inf, math.inf)

Iterative inorder implementation:

# python
def is_bst_inorder(root, allow_equal=False):
    stack = []
    prev = None
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None:
            if allow_equal:
                if node.val < prev:  # non-decreasing required
                    return False
            else:
                if node.val <= prev:  # strictly increasing required
                    return False
        prev = node.val
        node = node.right
    return True

Key points:

• Both traverse each node once: Time O(n). Stack/recursion depth up to O(h) where h is tree height; worst-case O(n) space.
• Duplicate policies:
  • Strict (no duplicates): use strict comparisons (< / >). Recursive bounds use exclusive bounds; inorder requires strictly increasing sequence.
  • Allow duplicates consistently on one side (e.g., duplicates allowed on right): choose allow_equal=True and interpret comparisons accordingly; for the recursive method you must decide if duplicates allowed equal to bound should go left or right and adjust bound propagation to avoid accepting duplicates on both sides. Inorder-based check with non-decreasing sequence only ensures duplicates exist but not which side; to enforce "duplicates must be on right", ensure when equal values occur they come from right-child placement by combining inorder check with node-child checks or use range checks that permit equality only on one side.
    Edge cases:
• Empty tree -> True
• Single node -> True
• All-equal values -> valid only if duplicates policy permits them on children consistently.

For the given tree:
1
/
2 3
/ \
4 5 6

(a) Preorder (root, left, right):
Sequence: 1, 2, 4, 5, 3, 6
Steps: Visit 1, go left → visit 2, go left → visit 4 (leaf), back up, visit 5, back to root, go right → visit 3, go right → visit 6.

(b) Inorder (left, root, right):
Sequence: 4, 2, 5, 1, 3, 6
Steps: From 1 go left to 2, go left to 4 → visit 4, back to 2 → visit 2, go right → visit 5, back to 1 → visit 1, go right to 3 → (left null) visit 3, go right → visit 6.

(c) Postorder (left, right, root):
Sequence: 4, 5, 2, 6, 3, 1
Steps: Traverse left subtree fully (4,5,2), then right subtree fully (6,3), then visit root 1.

(d) Level-order (breadth-first):
Sequence: 1, 2, 3, 4, 5, 6
Steps: Use a queue: enqueue 1, dequeue→visit 1, enqueue children 2,3; dequeue 2→visit, enqueue 4,5; dequeue 3→visit, enqueue 6; then visit 4,5,6.

Iterative vs recursive: Recursive implementations follow the same visit order because recursion encodes the traversal order via call-stack and call sequence. Iterative approaches use explicit data structures (stack for preorder/inorder/postorder, queue for level-order) to simulate that call-stack or breadth-first expansion. When implemented correctly the explicit push/pop/enqueue/dequeue ordering reproduces the same node visitation sequence as recursion.