How do you solve Increasing Order Search Tree on LeetCode?

Increasing Order Search Tree (LeetCode #897) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: In a BST, in-order traversal gives sorted order of values.

What is the brute force solution for Increasing Order Search Tree?

The brute force approach for Increasing Order Search Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves performing an in-order traversal of the binary search tree (BST) to collect the values in sorted order, and then reconstructing the tree in the desired format. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Increasing Order Search Tree?

Explain your thought process clearly while coding. Consider edge cases, such as an empty tree or a tree with only one node. Practice tree traversal techniques, as they are commonly used in tree-related problems.

What are common mistakes when solving Increasing Order Search Tree?

Forgetting to set the left child to null. Not handling the case of a single node correctly.

#897

Increasing Order Search Tree

Easy

StackTreeDepth-First SearchBinary Search TreeBinary TreeTree TraversalIn-Order Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a recursive in-order traversal to rearrange the nodes in place. This avoids the need for additional storage and builds the new tree structure directly.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to keep track of the last visited node.
2Step 2: Perform an in-order traversal, updating the left child to null and the right child to the next node.
3Step 3: Set the first visited node as the new root.

solution.py22 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def increasingBST(self, root: TreeNode) -> TreeNode:
10        self.prev = None
11        self.new_root = TreeNode(0)  # Dummy node
12        self.current = self.new_root
13        self.inorder(root)
14        return self.new_root.right
15
16    def inorder(self, node):
17        if node:
18            self.inorder(node.left)
19            node.left = None
20            self.current.right = node
21            self.current = node
22            self.inorder(node.right)

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(n) due to the recursive call stack in the worst case (for a skewed tree).

1In a BST, in-order traversal gives sorted order of values.
2Rearranging the tree to have only right children is a common tree manipulation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.