Problem
LeetCode 897: Increasing Order Search Tree (Easy)
Problem Statement: Given a binary search tree (BST), rearrange it (preserving the BST order) so that the lowest node is at the root and each node only has a right child. The result is like a sorted linked list.
The problem doesn’t mention any space requirements, and the tree has at most 100 nodes, so it’s easy to traverse the BST in order, save the values in a list, and build a new BST that meets the requirements. This is Approach 1 in the official solution. For a more challenging solution, we can save space by rearranging the tree in place, as in the official Approach 2. That’s the solution I’ll use.
Solution
The solution described here is based on this solution by lee215. It’s similar to the official Approach 2 solution, but the code is more concise without sacrificing readability.
In-order traversal
Since the goal is to rearrange the BST into a sorted list, the appropriate technique is in-order traversal. Here are the canonical steps for in-order binary tree traversal:
- Recursively traverse the left subtree
- Take an action on the current node
- Recursively traverse the right subtree
Based on the problem statement, we know that we’ll have to remove the left node in the middle step. But before we remove it, we have to save it somewhere, or we’ll lose all the nodes in the left subtree.
Tree traversal is commonly implemented using a recursive function. For example, we could implement a function to print a BST in sorted order using this in-order traversal algorithm:
if node is null, return
traverse(node.left)
print node value
traverse(node.right)
This function works by following left child links to the smallest node. Then it prints that node’s value. Then it follows that node’s right subtree using the same process. When it gets back to the root, it traverses the root’s right subtree using the same process. The call stack keeps track of where we are in the tree.
For the Increasing Order Search Tree problem, we can use the same pattern, but we’ll need some extra steps.
Pseudocode
The default code for this problem defines a function IncreasingBST that accepts a tree node (the root node) and returns a tree node (the root of the rearranged tree). Let’s create a recursive function with the same name and a second tree node parameter next that refers to the node to process after we’re done processing node. So the recursive function is:
TreeNode IncreasingBST(TreeNode node, TreeNode next)
To kick off the recursion, we’ll use return IncreasingBST(root, null): we’re at the root, and there’s no next node to process (once we process the root’s two subtrees, we’re done).
Here is a line-by-line explanation of the (pseudocode) function.
if node is null, return next
If the node parameter is null, it means we have followed a left or right child that is null. There’s nothing we can do with a null node, so we return the next node, which is the next node to process. In the case where the root is null, we’ll correctly return null, since next is null on the first call.
result = IncreasingBST(node.left, node)
Since we’re doing in-order traversal, we need to process the left subtree first, so we pass node.left as the first parameter. For the next parameter, we pass the current node, since a node in a BST follows its left child (if it has one) in ascending order. We’ll also save the result of this call to use later.
node.left = null
Now that we have followed the left child and saved the result, we can remove the left child, as required by the problem statement and the BST order.
node.right = IncreasingBST(node.right, next)
In in-order traversal, the right subtree is processed after the left subtree. Once we do this, we’re done with the parent node’s two subtrees, so the next parameter is the next value that was passed in.
return result
At the end of the function, we return the result that we saved in the first step. This is the result of the left subtree traversal, since the left subtree occurs first in BST order.
Example
It can take some work to follow the steps in a recursive algorithm. One technique that can help is to instrument the algorithm by writing to stdout at each step. This lets you see the program flow during the recursive calls.
Consider a BST that looks like this (root node 3 and only left children):
3
/
2
/
1
We want to transform it into this (root node 1 and only right children):
1
\
2
\
3
Here’s the output of the algorithm above running with instrumentation:
At root 3
Recursive call with node=3, node.left=2
Recursive call with node=2, node.left=1
Recursive call with node=1, node.left=null
Node is null; returning next=1
Saving result 1
Recursive call with node=1, node.right=null, next=2
Node is null; returning next=2
New node.right=2
Returning result 1
Saving result 1
Recursive call with node=2, node.right=null, next=3
Node is null; returning next=3
New node.right=3
Returning result 1
Saving result 1
Recursive call with node=3, node.right=null, next=null
Node is null; returning next=null
New node.right=null
Returning result 1
Code
Increasing Order Search Tree on GitHub
LeetCode Model Solutions
I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.