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
- In-Order Traversal: Perform an in-order traversal of the BST to visit nodes in ascending order.
- 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.
- Return New Root: The new root will be the leftmost node of the original tree.
Algorithm:
- Use a helper function
inOrderto perform in-order traversal. - Maintain a global variable
prevto keep track of the previously visited node during the traversal. - For each node, set its left child to
Noneand link it with the previous node’s right child. - Update
prevto 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.