897. Increasing Order Search Tree LeetCode Solution

In this guide, you will get 897. Increasing Order Search Tree LeetCode Solution with the best time and space complexity. The solution to Increasing Order Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Increasing Order Search Tree solution in C++
Increasing Order Search Tree solution in Java
Increasing Order Search Tree solution in Python
Additional Resources

897. Increasing Order Search Tree LeetCode Solution image

Problem Statement of Increasing Order Search Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Example 1:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Example 2:

Input: root = [5,1,7]
Output: [1,null,5,null,7]

Constraints:

The number of nodes in the given tree will be in the range [1, 100].
0 <= Node.val <= 1000

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

897. Increasing Order Search Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* increasingBST(TreeNode* root, TreeNode* tail = nullptr) {
    if (root == nullptr)
      return tail;

    TreeNode* ans = increasingBST(root->left, root);
    root->left = nullptr;
    root->right = increasingBST(root->right, tail);
    return ans;
  }
};
/* code provided by PROGIEZ */

897. Increasing Order Search Tree LeetCode Solution in Java

class Solution {
  public TreeNode increasingBST(TreeNode root) {
    return increasingBST(root, null);
  }

  private TreeNode increasingBST(TreeNode root, TreeNode tail) {
    if (root == null)
      return tail;

    TreeNode ans = increasingBST(root.left, root);
    root.left = null;
    root.right = increasingBST(root.right, tail);
    return ans;
  }
}
// code provided by PROGIEZ

897. Increasing Order Search Tree LeetCode Solution in Python

class Solution:
  def increasingBST(self, root: TreeNode, tail: TreeNode = None) -> TreeNode:
    if not root:
      return tail

    res = self.increasingBST(root.left, root)
    root.left = None
    root.right = self.increasingBST(root.right, tail)
    return res
 # code by PROGIEZ