FastPrepEvaluate an Addition and Subtraction Tree
Problems/Evaluate an Addition and Subtraction Tree

Evaluate an Addition and Subtraction Tree

Expedia logoExpedia● MediumNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks to evaluate a tree of + and - operators, and it talks about using separate node classes. The editorial keeps that class-based follow-up. We chose how the tree is written in preorder, the limits on the numbers, and the use of wide arithmetic. Our version is about 94% the same as the reported question.

tokens is the preorder serialization of one binary expression tree. The tokens + and - denote binary addition and subtraction nodes, each followed by its complete left subtree and then its complete right subtree. Every other token is a decimal integer literal with an optional leading minus.

Return the exact integer value at the root, preserving left-minus-right operand order. Use signed 64-bit arithmetic where the language requires a fixed integer type.

Source follow-up: model literals, addition nodes and subtraction nodes as separate classes sharing an evaluation interface. The first editorial approach demonstrates those classes; the second evaluates directly without constructing objects.

Function

evaluateExpression(tokens: String[]) → long

Examples

Example 1

tokens = ["-","+","7","3","4"]return = 6

The tree is (7+3)-4, which equals 6.

Example 2

tokens = ["-","10","-","5","2"]return = 7

The right subtree is 5-2=3, so the root is 10-3=7.

Constraints

  • 1 <= tokens.length <= 999.
  • Every token has length 1 through 11.
  • The tokens form exactly one complete valid binary prefix tree with operators + and -, and decimal integer leaves between -1000000000 and 1000000000. Literals have an optional leading minus and no leading zeroes except zero itself.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Lazy Binary Tree Inorder IteratorApple · PHONE SCREENApple interview questions
  • Binary Search Tree IteratorAtlassian · OAAtlassian interview questions
  • N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Filesystem Entity Total SizeGoogle · ONSITE INTERVIEWGoogle interview questions
  • In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
  • KV Store with Nested TransactionsApplied Intuition · PHONE SCREEN · ONSITE INTERVIEWApplied Intuition interview questions
  • Min StackDP World · ONSITE INTERVIEW
  • Lowest Common Ancestor Implemented with StackAmazon · ONSITE INTERVIEW
  • Kth Closest Element in a BSTLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Code Editor FoldingJane Street · ONSITE INTERVIEWJane Street interview questions

Interview reports that mention this question

  • Expedia New Grad SDE Oldest Loops: 4 Experiences (Part 3 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public long evaluateExpression(String[] tokens) {
        // Write your code here.
    }

}
Checking account…