Domain 1EasyCORE

Increasing Order Search Tree

The problem requires rearranging a binary search tree (BST) such that it becomes an increasing order search tree. In this new tree, the leftmost node should be the root, and every node should have no left child and only one right child. The input is the root of the original BST, and the output is the root of the rearranged tree.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Recursion

897. Increasing Order Search Tree

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 74.6%


Problem Breakdown

The problem requires rearranging a binary search tree (BST) such that it becomes an increasing order search tree. In this new tree, the leftmost node should be the root, and every node should have no left child and only one right child. The input is the root of the original BST, and the output is the root of the rearranged tree.

Inputs:

  • root: The root node of a binary search tree.

Outputs:

  • A new tree where nodes are arranged in increasing order with no left children and only right children.

Implicit Constraints or Tricky Edge Cases:

  • The tree can be empty (though the problem guarantees at least one node).
  • Nodes have values between 0 and 1000.
  • The tree is a valid binary search tree.

Intuition

A brute-force approach would involve first performing an in-order traversal to collect all nodes’ values, then creating a new tree from these values. However, this approach requires additional space proportional to the number of nodes (O(n)) and involves two separate operations: traversal and construction.

The key insight is that we can perform an in-order traversal while simultaneously rearranging the nodes in place. This way, we avoid the need for extra space and reduce the problem to a single pass through the tree.

Approach

  1. In-Order Traversal: Perform an in-order traversal of the BST to visit nodes in ascending order.
  2. Rearrange Nodes: During the traversal, rearrange each node such that it has no left child and only one right child. Keep track of the previously visited node to link it with the current node.
  3. Return New Root: The new root will be the leftmost node of the original tree.

Algorithm:

  • Use a helper function inOrder to perform in-order traversal.
  • Maintain a global variable prev to keep track of the previously visited node during the traversal.
  • For each node, set its left child to None and link it with the previous node’s right child.
  • Update prev to the current node after processing.

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once during the in-order traversal. Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack used for the depth-first search (DFS). In the worst case, this can be O(n) for a skewed tree.

Solution

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:
    dummy = TreeNode()  # Dummy node to act as the new root's parent
    prev = dummy
    
    def inOrder(node):
        nonlocal prev
        if not node:
            return
        
        inOrder(node.left)
        
        # Rearrange nodes
        node.left = None
        prev.right = node
        prev = node
        
        inOrder(node.right)
    
    inOrder(root)
    return dummy.right  # The new root is the right child of the dummy node

Edge Cases Handled

  • Single Node Tree: If the tree has only one node, it remains unchanged.
  • Skewed Trees (Left or Right): The algorithm handles both left-skewed and right-skewed trees correctly by maintaining the in-order property.
  • Balanced Trees: The approach works efficiently for balanced binary search trees as well.