Binary Tree Boundary Traversal
Updated
Problem statement
Return the binary tree’s boundary values in counterclockwise order, starting at the root. Include each boundary node exactly once, following this order:
- The root, if present.
- The left boundary excluding the root and leaves. Start at root.left, prefer a left child when present, otherwise take the right child. If the root has no left subtree, this part is empty.
- Every leaf from left to right. A leaf has no children. A root that is itself a leaf has already been included and must not be repeated.
- The right boundary excluding the root and leaves, in reverse. Start at root.right, prefer a right child when present, otherwise take the left child. If the root has no right subtree, this part is empty.
Different nodes may have the same value; include each such node’s value in its proper position. Do not deduplicate by numeric value. Return an empty array for an empty tree and leave the tree unchanged.
Function
boundaryTraversal(root: TreeNode) → int[]Examples
Example 1
root = [1,2,3,4,5,6,7,null,null,8,9]return = [1,2,4,8,9,6,7,3]Start with root 1. The non-leaf left boundary is [2], leaves from left to right are [4,8,9,6,7], and the reversed non-leaf right boundary is [3]. Combining them gives [1,2,4,8,9,6,7,3].
Example 2
root = [1,null,2,null,3,null,4]return = [1,4,3,2]The root has no left subtree, so its left-boundary part is empty. The sole leaf is 4, and the reversed non-leaf right boundary is [3,2]. The result is [1,4,3,2], with each node included once.
Constraints
- For this exercise, assume the input is a valid finite binary tree with between 0 and 300 non-null nodes.
- Every non-null node value is between 1 and 100000, inclusive.
More Morgan Stanley Onsite Interview questions
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
- Maximum Edge Removals for Two TravelersONSITE INTERVIEW · Seen Oct 2025
- Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
- Count Ideal ArraysONSITE INTERVIEW · Seen Aug 2023
- Distinct Palindrome PartitionsONSITE INTERVIEW · Seen Aug 2023
- LFU Cache OperationsONSITE INTERVIEW · Seen Aug 2023
- All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Maximum Sum Among Longest Root-to-Leaf PathsAmazon · ONSITE INTERVIEW
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Onion-Peel Layers of a Binary TreeeBay · ONSITE INTERVIEWeBay interview questions
- Match a Descendant Selector in a DOM TreeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley Apprenticeship and Tech Interviews: 6 Experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)