Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 897: Increasing Order Search Tree

By Duncan Smith Feb 10 0

LeetCode 2021

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.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode 11: Container With Most Water February 24, 2021
  • LeetCode 47: Permutations II February 17, 2021
  • LeetCode 897: Increasing Order Search Tree February 10, 2021
  • LeetCode 394: Decode String February 3, 2021
  • LeetCode 1022: Sum of Root To Leaf Binary Numbers January 27, 2021
  • LeetCode 1288: Remove Covered Intervals January 20, 2021
  • LeetCode 227: Basic Calculator II January 13, 2021
  • A Project for 2021 January 6, 2021
  • Lessons from the 2020 LeetCode Monthly Challenges December 30, 2020
  • Quora: Are Math Courses Useful for Competitive Programming? December 23, 2020
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2021 Duncan Smith