[Solved] 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.

Question

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:

Machine Learning Projects
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:

Machine Learning Projects
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

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def make_list(self,root,l):
        if root == None:
            return 
        
        self.make_list(root.left,l)
        l.append(root.val)
        self.make_list(root.right,l)
        
        
    def increasingBST(self, root: TreeNode) -> TreeNode:
        l = []
        self.make_list(root,l)
        ans = TreeNode(0)
        curr = ans
        
        for i in l:
            curr.left = None
            curr.right = TreeNode(i)
            curr = curr.right
        
        return ans.right
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 517

Leave a Reply

Your email address will not be published. Required fields are marked *