FastPrepVerify Postorder Sequence of a BST
Problems/Verify Postorder Sequence of a BST

Verify Postorder Sequence of a BST

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A review of a Microsoft software engineering internship lists one coding question. Decide whether an array could be the postorder sequence of some binary search tree. The review does not say which step it came from. Its interviews had live coding, followed by a talk about how fast and how memory-hungry the solution was.

The report does not say whether values can repeat or give any limits. Here all values are distinct, so smaller values go left and larger ones go right. The array has 1 to 500 values.

Our version is about 90% the same as the reported question.

You are given an array postorder of distinct integers. Return true if it is the postorder traversal of some binary search tree, and false otherwise.

In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. A postorder traversal lists the left subtree, then the right subtree, then the node itself.

After solving it, work out the time and extra space your solution uses.

Function

verifyPostorder(postorder: int[]) → boolean

Examples

Example 1

postorder = [2,4,3,8,7,5]return = true

The last value, 5, is the root. The values before it split into 2, 4, 3 (all smaller than 5, the left subtree) and 8, 7 (all larger, the right subtree). In 2, 4, 3 the root is 3 with left part 2 and right part 4. In 8, 7 the root is 7 with an empty left part and right part 8. Every check passes, so the answer is true.

Example 2

postorder = [7,4,6,5]return = false

The root is 5. The first value, 7, is already larger than 5, so the left subtree is empty and all of 7, 4, 6 must be in the right subtree. But 4 is smaller than 5, so no binary search tree has this postorder. The answer is false.

Example 3

postorder = [10]return = true

A single value is the postorder of a one-node tree, so the answer is true.

Constraints

  • 1 <= postorder.length <= 500
  • 1 <= postorder[i] <= 10^4
  • All values in postorder are distinct.

More Microsoft Onsite Interview questions

  • Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
  • Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
  • Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
  • Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
  • Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
  • Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
  • Coin ChangeONSITE INTERVIEW · Seen Oct 2026
  • Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
  • Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
  • Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026

Similar questions at other companies

  • Ternary Expression to Binary TreeNutanix · ONSITE INTERVIEWNutanix interview questions
  • Construct a Tree from Level-Order and Inorder TraversalsSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Rebuild a Binary Tree From Two WalksAdobe · PHONE SCREENAdobe interview questions
  • Build an Expression Tree from PostfixPeopleStrong · PHONE SCREENPeopleStrong interview questions
  • Construct a Tree from Level-Order and Inorder TraversalsAmazon · PHONE SCREEN
  • Filesystem Entity Total SizeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Single-Pass S-Expression ParserBaseten · ONSITE INTERVIEWBaseten interview questions
  • Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
  • Kth Closest Element in a BSTLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Parse Nested HTML into a TreeApple · ONSITE INTERVIEWApple interview questions

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // Write your code here.
    }
}
Checking account…