Binary Tree Preorder Traversal
Updated
Problem statement
Return the node values of a binary tree in preorder: visit the root, then its entire left subtree, then its entire right subtree.
Return an empty array for an empty tree. Include every node, even when several nodes have the same value.
Follow-up: explain both a recursive implementation and an iterative implementation using an explicit stack.
Function
preorderTraversal(root: TreeNode) → List<Integer>Examples
Example 1
root = [6,4,8,1,5,null,9]return = [6,4,1,5,8,9]Visit root 6, then the complete left subtree in the order 4,1,5, then the right subtree in the order 8,9.
Example 2
root = [2,null,3,4]return = [2,3,4]The root 2 has no left child. Visit its right child 3, then the left child 4 of node 3.
Constraints
- For this exercise, assume the tree has between 0 and 500 nodes.
- For this exercise, assume -1000000 <= node values <= 1000000.
- The input is a valid finite binary tree.
More Morgan Stanley interview questions
- Unique Grid PathsPHONE SCREEN · Seen Oct 2026
- Reverse an IntegerPHONE SCREEN · Seen Jul 2024
- Second and Third Distinct Order ValuesPHONE SCREEN · Seen Jul 2024
- Find a Target-Sum SubarrayPHONE SCREEN · Seen Jan 2024
- Two SumPHONE SCREEN · Seen Jan 2024
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Three-Resource 0/1 KnapsackOA · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Maximum Total of Nonadjacent RatingsOA · Seen Jul 2026
Similar questions at other companies
- Inorder Traversal Without RecursionAdobe · PHONE SCREENAdobe interview questions
- Binary Tree Inorder TraversalBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
- Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
- Delete a Filesystem TreeDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
- Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
- Kth Smallest Value in a BSTExpedia · PHONE SCREEN · ONSITE INTERVIEWExpedia interview questions
- Kth Smallest Element in a BSTNutanix · PHONE SCREENNutanix interview questions
- Recover a Tree from Preorder Depth EncodingSuperhuman · PHONE SCREENSuperhuman interview questions
- Binary Tree Preorder TraversalAnduril · ONSITE INTERVIEWAnduril 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 Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)