We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Increasing Order Search Tree

Number: 933

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node becomes the new root. Every node in the new tree should have no left child and only one right child.

Key Insights

  • Use in-order traversal to access nodes in ascending order.
  • As you visit each node, adjust pointers: remove the left child and attach the node as the right child of the previously processed node.
  • Using a dummy node simplifies the process by providing a fixed starting point for the new tree structure.
  • Recursive in-order traversal is straightforward and leverages the inherent properties of a BST.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n) in the worst-case scenario due to recursion stack and the additional space used for the new tree structure.

Solution

Perform an in-order traversal to visit the nodes in ascending order. Use a dummy node to initiate the new tree and maintain a pointer (current) to the most recent node added. For each visited node, set the left pointer to null and attach it as the right child of current. This approach rearranges the tree in one pass without the need for additional complex data structures.

Code Solutions

# 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 increasingBST(self, root: TreeNode) -> TreeNode:
        # Create a dummy node to serve as the anchor for the new tree
        dummy = TreeNode(0)
        current = dummy
        
        # Define an in-order traversal helper function
        def in_order_traversal(node):
            nonlocal current
            if not node:
                return
            # Traverse left subtree
            in_order_traversal(node.left)
            
            # Process the current node: detach left child and attach it to the new tree
            node.left = None
            current.right = node
            current = node
            
            # Traverse right subtree
            in_order_traversal(node.right)
        
        in_order_traversal(root)
        return dummy.right
← Back to All Questions