Verify Postorder Sequence of a BST
Updated
Problem statement
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[]) → booleanExamples
Example 1
postorder = [2,4,3,8,7,5]return = trueThe 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 = falseThe 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 = trueA single value is the postorder of a one-node tree, so the answer is true.
Constraints
1 <= postorder.length <= 5001 <= postorder[i] <= 10^4- All values in
postorderare 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