[Solution]Problem 61:Increasing Order Search Tree [Apple]
Trees, Recursion, Data Structure, Traversal
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Take the next step by subscribing here
Let’s get right into this
This problem can be found as problem 897. Increasing Order Search Tree
For my Python people, there is a way to do this using ‘yield’ which might give slightly better performance, but that is a language-specific trick, so my solution is not going to cover that. It’s not important enough to make a meaningful difference in your interviews.
Problem
Given the root
of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.
Example 1:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
Example 2:
Input: root = [5,1,7]
Output: [1,null,5,null,7]
Constraints:
The number of nodes in the given tree will be in the range
[1, 100]
.0 <= Node.val <= 1000
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.