Convert a Binary Search Tree (BST) into a skewed tree in either increasing or decreasing order

A Binary Search Tree (BST) can be converted into a skewed tree, essentially a sorted linked list, by performing an in-order traversal and strategically re-wiring the node pointers. This process leverages the inherent sorted property of a BST's in-order traversal to create a new structure where all nodes are linked sequentially, either in increasing (right-skewed) or decreasing (left-skewed) order.

Mechanics and "Why"

The core idea is to flatten the tree into a linear structure by modifying its left and right pointers during a traversal.

* Increasing Order (Right-Skewed):
1. Perform an in-order traversal (left child -> current node -> right child).
2. Maintain a prev pointer, which tracks the last node processed in the desired order, and a head pointer for the start of the new skewed tree.
3. For each current_node visited:
* Set current_node.left = None to eliminate its left child and ensure the tree skews to the right.
* If prev exists, set prev.right = current_node to link the previous node to the current one.
* If head is not yet set (i.e., this is the very first node processed), set head = current_node.
* Update prev = current_node.
* Decreasing Order (Left-Skewed):
* This is achieved by performing a reverse in-order traversal (right child -> current node -> left child).
* For each current_node, set current_node.right = None and link prev.left = current_node.

This modification is performed in-place, meaning no new nodes are created; only existing pointers are reassigned.

Complexity:
* Time Complexity: O(N), as every node in the BST must be visited exactly once.
* Space Complexity: O(H) for the recursion stack, where H is the height of the BST. In the worst case (a completely skewed BST), H can be N, leading to O(N) space.

Example and Trade-offs

Here's a Python example for converting a BST into an increasing (right-skewed) tree:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def convert_bst_to_skewed(root):
    # Use a list to hold the 'prev' node and the 'head' of the new skewed list
    # so they can be modified by recursive calls.
    state = [None, None] # [prev_node, head_node]
def _inorder_flatten(node):
        if not node:
            return
_inorder_flatten(node.left)
# Process current node
        if not state[1]: # If head is not set, this is the first node
            state[1] = node
        else:
            state[0].right = node # Link previous node to current
node.left = None # Ensure left child is None for right-skewed
        state[0] = node # Update prev_node to current
_inorder_flatten(node.right)
_inorder_flatten(root)
    return state[1] # Return the new head of the skewed tree

Trade-offs: While efficient in time and space, this operation fundamentally changes the data structure. A BST offers logarithmic time complexity (O(log N)) for search, insertion, and deletion in a balanced tree. Converting it to a skewed tree (a linked list) degrades these operations to linear time complexity (O(N)), making it unsuitable for scenarios requiring efficient searching or balancing.

In the interview, also mention…

In the interview, also mention that while this specific transformation is rare in production data systems, understanding pointer manipulation and tree traversals is crucial for optimizing data structures like B-trees (used in databases like Snowflake for micro-partitions and indexing) or managing distributed data structures where node relationships are critical for performance and data integrity. This problem tests fundamental data structure manipulation skills.