Increasing Order Search Tree

Problem

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.

Examples

Example 1

![](https://assets.leetcode.com/uploads/2020/11/17/ex1.jpg)

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

![](https://assets.leetcode.com/uploads/2020/11/17/ex2.jpg)

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

Solution

Method 1 – Inorder Traversal with Re-linking

Intuition

The in-order traversal of a BST yields nodes in increasing order. By visiting nodes in-order and re-linking them so each node has no left child and only a right child, we can build the required tree.

Approach

1. Perform an in-order traversal of the BST.
2. For each visited node:
   • Set its left child to null.
   • Link it as the right child of the previously visited node.
3. Use a dummy node to simplify linking.
4. Return the right child of the dummy node as the new root.

Code

C++

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode dummy(0), *cur = &dummy;
        inorder(root, cur);
        return dummy.right;
    }
private:
    void inorder(TreeNode* node, TreeNode*& cur) {
        if (!node) return;
        inorder(node->left, cur);
        node->left = nullptr;
        cur->right = node;
        cur = node;
        inorder(node->right, cur);
    }
};

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func increasingBST(root *TreeNode) *TreeNode {
    dummy := &TreeNode{}
    cur := dummy
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        node.Left = nil
        cur.Right = node
        cur = node
        inorder(node.Right)
    }
    inorder(root)
    return dummy.Right
}

Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0), cur = dummy;
        cur = inorder(root, cur);
        return dummy.right;
    }
    private TreeNode inorder(TreeNode node, TreeNode cur) {
        if (node == null) return cur;
        cur = inorder(node.left, cur);
        node.left = null;
        cur.right = node;
        cur = node;
        return inorder(node.right, cur);
    }
}

Kotlin

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    fun increasingBST(root: TreeNode?): TreeNode? {
        val dummy = TreeNode(0)
        var cur = dummy
        fun inorder(node: TreeNode?) {
            if (node == null) return
            inorder(node.left)
            node.left = null
            cur.right = node
            cur = node
            inorder(node.right)
        }
        inorder(root)
        return dummy.right
    }
}

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        dummy = TreeNode(0)
        cur = dummy
        def inorder(node: TreeNode):
            nonlocal cur
            if not node:
                return
            inorder(node.left)
            node.left = None
            cur.right = node
            cur = node
            inorder(node.right)
        inorder(root)
        return dummy.right

Rust

// Definition for a binary tree node.
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}
pub struct Solution;
impl Solution {
    pub fn increasing_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let dummy = Rc::new(RefCell::new(TreeNode::new(0)));
        let mut cur = dummy.clone();
        fn inorder(node: Option<Rc<RefCell<TreeNode>>>, cur: &mut Rc<RefCell<TreeNode>>) {
            if let Some(n) = node {
                let left = n.borrow_mut().left.take();
                inorder(left, cur);
                cur.borrow_mut().right = Some(n.clone());
                *cur = n.clone();
                let right = cur.borrow_mut().right.as_ref().unwrap().borrow_mut().right.take();
                inorder(right, cur);
            }
        }
        inorder(root, &mut cur);
        dummy.borrow_mut().right.clone()
    }
}

TypeScript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}
class Solution {
  increasingBST(root: TreeNode | null): TreeNode | null {
    const dummy = new TreeNode(0);
    let cur = dummy;
    function inorder(node: TreeNode | null) {
      if (!node) return;
      inorder(node.left);
      node.left = null;
      cur.right = node;
      cur = node;
      inorder(node.right);
    }
    inorder(root);
    return dummy.right;
  }
}

Complexity

• ⏰ Time complexity: O(n) — Each node is visited once during in-order traversal.
• 🧺 Space complexity: O(h) — Call stack for recursion, where h is the height of the tree.