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:
[1, 100].0 <= Node.val <= 1000This approach involves performing an in-order traversal to visit the nodes of the tree in sorted order. As we visit each node, we rearrange the nodes to form a new tree where each node only has a right child.
We will use a dummy node that helps us easily chain the nodes in the desired manner. During the traversal, we append each node to the right of the previous node.
In the Python solution, we define a helper function inorder that performs an in-order traversal. We pass each node to this function to rearrange the nodes by severing the left child and linking the nodes to the right child of the current node pointed by self.cur.
The dummy node acts as a placeholder to return the new root of the tree.
C++
Java
JavaScript
C
C#
Time Complexity: O(n), where n is the number of nodes, as we visit each node once.
Space Complexity: O(n), due to the recursion stack space where n is the number of nodes.
A space-optimized approach to perform in-order traversal without recursion or a stack is Morris Traversal. This involves temporarily modifying the tree structure by linking the in-order predecessor of each node to the node itself, allowing us to traverse the tree without additional space.
During the traversal, we reconstruct the tree in the desired form by altering the left and right pointers.
The Python solution employs Morris Traversal to achieve O(1) space complexity. We use a while loop to traverse the tree while altering the pointers as described. When there's a left subtree, we find the predecessor, link it, and then follow the same logic until the tree is reconstructed in the desired order.
C++
Java
JavaScript
C
C#
Time Complexity: O(n), as each node is processed a constant number of times (at most twice).
Space Complexity: O(1), as we are not using any extra space other than a couple of pointers.
| Approach | Complexity |
|---|---|
| Approach 1: In-Order Traversal with Recursion | Time Complexity: O(n), where n is the number of nodes, as we visit each node once. Space Complexity: O(n), due to the recursion stack space where n is the number of nodes. |
| Approach 2: Morris In-Order Traversal | Time Complexity: O(n), as each node is processed a constant number of times (at most twice). Space Complexity: O(1), as we are not using any extra space other than a couple of pointers. |
Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python • NeetCode • 94,636 views views
Watch 9 more video solutions →Practice Increasing Order Search Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor