Solve tree equality and valid parentheses

You are asked to solve two independent coding questions.

1) Compare two binary trees for equality

Given the roots of two binary trees p and q, return true if they are structurally identical and all corresponding nodes have the same value; otherwise return false.

Input: Two tree roots p, q (each node has val, left, right).

Output: Boolean.

Constraints (typical):

• 0 <= number_of_nodes <= 10^4
• Node values fit in 32-bit signed integer.

2) Validate bracket/parentheses string

Given a string s consisting only of the characters '(' , ')' , '{' , '}' , '[' , ']', determine whether the input string is valid.

A string is valid if:

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding earlier open bracket.

Input: String s.

Output: Boolean.

Constraints (typical):

• 0 <= |s| <= 10^5

Additional requirement

After implementing each solution, write a few test cases that cover normal cases and edge cases.

Compare Binary Trees For Equality

Trees are represented as [value,left,right] or None. Return whether two trees have identical structure and values.

Examples

Example 1

Input: ([1,[2,None,None],[3,None,None]], [1,[2,None,None],[3,None,None]])
Output: True

Explanation: Same structure and values.

Example 2

Input: ([1,[2,None,None],None], [1,None,[2,None,None]])
Output: False

Explanation: Different structure is not equal.

Hints

1. Clarify edge cases before coding.
2. Keep the return value deterministic.

Validate Bracket String

Return whether a bracket string is valid with matching bracket types and order.

Examples

Example 1

Input: ('()[]{}',)
Output: True

Explanation: Every bracket closes correctly.

Example 2

Input: ('([)]',)
Output: False

Explanation: Incorrect nesting is invalid.

Hints

1. Clarify edge cases before coding.
2. Keep the return value deterministic.