Katkat
Back

Solve Bracket Matching and Tree Width

ByteDanceBackend Engineer · HR Screen
HardBackend EngineerHR ScreenCoding & Algorithms

Last updated

This problem tests string manipulation and tree traversal techniques by requiring the validation of complex bracket sequences and the calculation of the maximum horizontal distance between nodes at the same level of a binary tree.

Part 1: Bracket Validation

Given a string containing only characters '(', ')', '[', ']', '{', and '}', write a function is_valid(s: str) -> bool that returns true if the input string is valid. A string is valid if every opening bracket is closed by the same type of bracket in the correct order, and all brackets are closed.

Part 2: Binary Tree Width

Given the root of a binary tree, write a function tree_width(root) -> int that calculates the maximum width of the tree. The width of a level is defined as the distance between the leftmost and rightmost nodes (including null nodes that sit between them).

The position of a node at index i is determined as follows:

  • Left child: 2 * i
  • Right child: 2 * i + 1

Example

Input (Tree): 1 /
3 2 /
5 9

  • Level 0: Node 1 (index 0). Width = 0 - 0 + 1 = 1.
  • Level 1: Nodes 3, 2 (indices 0, 1). Width = 1 - 0 + 1 = 2.
  • Level 2: Nodes 5, 9 (indices 0, 3). Width = 3 - 0 + 1 = 4.

Result: 4

Constraints

  • The tree contains between 0 and 3000 nodes.
  • The indices can grow large; ensure your solution handles integer overflow if the language requires it.
  • Provide a clean class definition for TreeNode.

Hints

Hint 1

For bracket matching, use a stack to keep track of opening brackets and verify the top of the stack matches the closing bracket encountered.

Hint 2

For tree width, perform a Level Order Traversal (BFS) and store the index of each node alongside its reference to easily calculate the span per level.

Hint 3

The width at any level is `rightmost_index - leftmost_index + 1`; ensure you handle potential overflow by normalizing indices at each level.

Follow-up questions

  • How would you modify the bracket validator to handle optional characters that do not require closing (e.g., tags)?
  • What is the time and space complexity of the width calculation, and can you optimize the space if the tree is very skewed?
  • How would you handle a scenario where the binary tree is actually a general graph that could contain cycles?