PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches
|Home/Coding & Algorithms/Waymo

Serialize Expression Tree Minimizing Parentheses

Last updated: May 2, 2026

Quick Overview

This question evaluates proficiency with binary expression trees, operator precedence and associativity, and the ability to serialize an abstract syntax tree into an infix string using the minimum necessary parentheses.

  • medium
  • Waymo
  • Coding & Algorithms
  • Software Engineer

Serialize Expression Tree Minimizing Parentheses

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a binary expression syntax tree, serialize it into an infix string using the minimum number of parentheses required to preserve the tree's evaluation semantics. Each node is one of: - A variable leaf, represented by a non-empty identifier such as `a`, `x`, or `foo` - A binary operator node whose operator is one of `+`, `-`, `*`, `/` and whose left and right children are valid expression nodes Use standard arithmetic precedence: 1. `*` and `/` have higher precedence than `+` and `-` 2. Operators are evaluated left to right when precedence is the same Return a string representation of the expression with unnecessary parentheses removed, but do not change the meaning of the original expression tree. Examples: - Tree for `(a + b) * c` should serialize as `(a+b)*c` - Tree for `a + (b * c)` should serialize as `a+b*c` - Tree for `a - (b + c)` should serialize as `a-(b+c)` - Tree for `(a - b) - c` should serialize as `a-b-c` - Tree for `a / (b * c)` should serialize as `a/(b*c)` Implement a function such as: `string serialize(Node root)` where `Node` contains either a variable name or an operator with left and right children.

Quick Answer: This question evaluates proficiency with binary expression trees, operator precedence and associativity, and the ability to serialize an abstract syntax tree into an infix string using the minimum necessary parentheses.

Related Interview Questions

  • Expand Nested Repetition Expressions - Waymo (medium)
  • Find Shortest Paths to Target Nodes - Waymo (medium)
  • Implement Safe Average Function - Waymo (medium)
  • Find Shortest Knight Path - Waymo (medium)
  • Implement Fibonacci generator, balanced BST, frozenset - Waymo (medium)
Waymo logo
Waymo
Feb 25, 2026, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
2
0
Loading...

Given a binary expression syntax tree, serialize it into an infix string using the minimum number of parentheses required to preserve the tree's evaluation semantics.

Each node is one of:

  • A variable leaf, represented by a non-empty identifier such as a , x , or foo
  • A binary operator node whose operator is one of + , - , * , / and whose left and right children are valid expression nodes

Use standard arithmetic precedence:

  1. * and / have higher precedence than + and -
  2. Operators are evaluated left to right when precedence is the same

Return a string representation of the expression with unnecessary parentheses removed, but do not change the meaning of the original expression tree.

Examples:

  • Tree for (a + b) * c should serialize as (a+b)*c
  • Tree for a + (b * c) should serialize as a+b*c
  • Tree for a - (b + c) should serialize as a-(b+c)
  • Tree for (a - b) - c should serialize as a-b-c
  • Tree for a / (b * c) should serialize as a/(b*c)

Implement a function such as:

string serialize(Node root)

where Node contains either a variable name or an operator with left and right children.

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Waymo•More Software Engineer•Waymo Software Engineer•Waymo Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.