algoadvance

Given the root of a binary search tree, rearrange the tree in an “in-order” manner such that the left child of all nodes becomes None and the right child points to the next node in the in-order sequence. Essentially, flatten the BST so that it becomes an increasingly ordered singly linked list.

Example:

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]

Constraints:

Clarifying Questions

  1. Q: Are there any duplicates in the BST? A: Since it is a BST, there will be no duplicate values.

  2. Q: Should the values in the new tree be sorted in increasing order? A: Yes, the values should appear in increasing order, following an in-order traversal.

  3. Q: Is it allowed to modify the existing tree, or should we create a new tree structure? A: We can rearrange the nodes of the existing tree or create a new tree structure as required by the problem.

Strategy

  1. In-order Traversal: Perform an in-order traversal of the BST. During the traversal, capture the nodes in the order processed by in-order, which naturally gives us the nodes in increasing order.
  2. Re-build Tree: Use the captured nodes to re-link the tree such that each node’s left child is None and right child points to the next node in the sequence.

Here’s a step-by-step breakdown:

Code

# 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

def increasingBST(root: TreeNode) -> TreeNode:
    def in_order_traversal(node):
        if node:
            yield from in_order_traversal(node.left)
            yield node
            yield from in_order_traversal(node.right)
    
    # We create a dummy node to serve as the previous node initially
    dummy = TreeNode(-1)
    prev = dummy
    
    # Traverse the tree in order and link nodes appropriately
    for node in in_order_traversal(root):
        node.left = None  # Nullify the left child
        prev.right = node
        prev = node  # Move prev to the current node
    
    # The right child of dummy points to the newly created tree head
    return dummy.right

# This test setup assumes a TreeNode class and the input structure similar to provided problem example

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is due to the in-order traversal which visits each node exactly once. The space complexity, considering the function call stack, is O(h) where h is the height of the tree, due to the recursion stack. In the worst case (a highly unbalanced tree), this can become O(n).

Try our interview co-pilot at AlgoAdvance.com