Trees and Binary Search Trees Questions

I’d state the rule clearly: duplicates are allowed only in the right subtree. That means for every node, the left subtree must be strictly smaller, and the right subtree may be greater than or equal to the node value.

class Solution:
    def isValidBST(self, root):
        def dfs(node, low, high):
            if not node:
                return True

            # low is exclusive, high is inclusive on the right side rule
            if node.val <= low or node.val > high:
                return False

            return dfs(node.left, low, node.val - 1) and dfs(node.right, node.val, high)

        return dfs(root, float('-inf'), float('inf'))

Important note: subtracting 1 can break on integer boundaries. A safer version is to pass inclusivity flags instead of arithmetic bounds.

Safer approach

• Left subtree: values < node.val
• Right subtree: values >= node.val
• Use low and high with open/closed interval semantics.

Edge cases

• INT_MIN / INT_MAX
• Single-node trees
• Duplicate placed on the wrong side
• Deep trees causing recursion depth issues

Naive implementations often fail by checking only parent-child ordering, which misses violations deeper in the tree.

A binary tree’s costs depend heavily on shape. In a balanced tree, height is O(log n); in a degenerate tree, height becomes O(n), so many operations degrade from logarithmic to linear.

Common operations

• Search / Insert / Delete in BST: O(h), where h is height.
  • Balanced: O(log n)
  • Degenerate: O(n)
• Traversal (inorder/preorder/postorder): O(n) time in both cases, because every node is visited.
  • Space: O(h) recursion/stack, so O(log n) balanced, O(n) skewed.
• Lowest Common Ancestor:
  • In a BST, a single walk from root is O(h).
  • Balanced: O(log n)
  • Degenerate: O(n)

Why practical cost differs
Even when big-O looks similar, constant factors and memory behavior matter. Search may stop early if the key is near the root, while delete often does search plus a successor/predecessor lookup and pointer rewiring. Traversal always touches all nodes, but recursive traversal can overflow the stack on deep trees. LCA is especially sensitive: in a BST it can be fast, but in a general binary tree you may need to explore both branches unless you have preprocessing. For backend systems, that’s why self-balancing trees or indexed structures matter: they protect latency under adversarial or sorted insert patterns.

I define the height of an empty tree as -1 and a single-node tree as 0, which means height is the number of edges on the longest path from root to leaf.

def tree_height(root):
    if not root:
        return -1
    return 1 + max(tree_height(root.left), tree_height(root.right))

This runs in linear time because each node is visited exactly once. The recursion does constant work per node: compute left height, right height, then take the maximum. Space complexity is O(h) for the call stack, where h is tree height.

For backend interviews, I also mention that this definition is important to keep formulas consistent, especially when comparing balanced and skewed trees.

To validate a BST, I check that every node respects the full allowed range, not just its immediate children.

Why child-only checks fail: a node can be greater than its parent but still violate an ancestor constraint. For example, a value in the right subtree of 10 could be 6; it is greater than its parent 5, but still invalid because it must also be > 10.

Min-max range approach: pass down lower and upper bounds during recursion. This is the most direct and reliable method.

Inorder approach: inorder traversal of a valid BST should produce a strictly sorted sequence. That is elegant and simple, but it depends on traversal state and is less explicit about where the violation occurs.

For interviews, I usually mention both, then choose min-max for clarity and easy reasoning.

I’d design a versioned binary encoding with a small header, explicit field tags, and bounded parsing. My default choice would be a protobuf-like format: compact on the wire, fast to parse, and tolerant of added fields.

Format design

• Header: magic bytes + schema version + payload type
• Body: node records with field IDs for value, left/right child references, and optional metadata
• Use length prefixes for strings/byte arrays to avoid delimiter ambiguity
• Include a checksum or integrity hash if messages cross regions

Safety for untrusted input

• Enforce max depth, max node count, and max payload size
• Reject unknown enum values and invalid references
• Parse iteratively where possible to avoid stack blowups
• Never use native object deserialization

Comparison

• JSON: easy to debug and version, but verbose and slower to parse; null markers for trees inflate size.
• Delimiter-based: compact and simple, but fragile when values contain delimiters and harder to evolve safely.
• Binary encoding: best for performance and size; requires careful schema management.

For schema evolution, I’d make all fields optional, reserve removed field IDs, and keep backward-compatible readers that ignore unknown fields. That gives us compactness, resilience, and safe interoperability across services and regions.