Katkat
Back

Solve tree equality and valid parentheses

Deutsche BankSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem set evaluates core skills in data structures and algorithmic reasoning, specifically binary tree structural equality and bracket-matching for strings, testing understanding of tree traversal, recursion, and stack-based parsing.

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.