Increasing Order Search Tree

Increasing Order Search Tree

What is this problem about?

The Increasing Order Search Tree coding problem asks you to rearrange a given Binary Search Tree (BST) into a skewed tree. In the new tree, every node should only have a right child, and no left child. The nodes must appear in increasing order of their values, which means the resulting structure is effectively a linked list composed of tree nodes.

Why is this asked in interviews?

Companies like Google and Amazon use this "Easy" question to test a candidate's understanding of tree traversal properties. Since it's a BST, an Inorder Traversal naturally visits the nodes in sorted order. The problem evaluates your ability to manipulate pointers during a traversal to restructure a data structure without losing references to nodes. It checks for a solid grasp of recursion and pointer management.

Algorithmic pattern used

The problem is solved using the Inorder Traversal (Left-Root-Right) pattern.

1. Perform an inorder traversal of the original BST.
2. During the traversal, instead of just printing the values, you modify the pointers.
3. Maintain a "current" pointer to the last node added to the new skewed tree.
4. For each node visited in the inorder sequence:
   • Set its left child to null.
   • Make it the right child of the "current" node.
   • Move the "current" pointer to this node.

Example explanation

Original BST:

    5
   / 
  3   6

1. Inorder traversal visits: 3, 5, 6.
2. Start with a dummy node. Current points to dummy.
3. Visit 3: dummy.right = 3, 3.left = null. current = 3.
4. Visit 5: 3.right = 5, 5.left = null. current = 5.
5. Visit 6: 5.right = 6, 6.left = null. current = 6. Result: 3 -> 5 -> 6 (all right children).

Common mistakes candidates make

• Losing Nodes: Modifying pointers in a way that breaks the traversal path before the recursion can continue.
• Memory Overhead: Storing all node values in a list first and then creating new nodes ($O(N)$ extra space). While valid, interviewers prefer an in-place pointer modification.
• Left Pointers: Forgetting to explicitly set the left child of each node to null in the new tree.

Interview preparation tip

Always remember the BST property: Inorder = Sorted. When you need to do something with BST nodes in a specific order, inorder traversal is almost always the starting point. Practice doing it "in-place" to show off your memory management skills.