LeetCode problems solved in Kotlin

LeetCode problems solved in Kotlin.md

LeetCode problems solved in Kotlin

Notes

• This is a work in progress.
• The content is optimized to retrieve necessary information quickly, so the content is in this single page, searchable by tags and using full-text search.

897. Increasing Order Search Tree

Description

Leetcode 897 — 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 becomes the new root, and every node has no left child and only one right child.
• In other words, turn the binary search tree (which may have left and right children) into a linked list–like structure where each node points only to its successor using right.

Node Definition

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

Solution

class Solution {
    fun increasingBST(root: TreeNode?): TreeNode? {
        return rearrange(root, null)
    }

    private fun rearrange(
        node: TreeNode?, 
        next: TreeNode?,
    ): TreeNode? {
        if (node == null) {
            return next
        }
        val newRoot = rearrange(node.left, node)
        node.left = null
        node.right = rearrange(node.right, next)
        return newRoot
    }
}

This recursive, declarative solution:

• Visits nodes in in-order sequence (left → node → right)
• Removes all left links
• Threads nodes through their right pointers to form an increasing right-skewed tree

Examples

Example 1

Input

    2
   / \
  1   3

Output

1
 \
  2
   \
    3

Example 2

Input

        5
       / \
      3   6
     / \   \
    2   4   8
   /       / \
  1       7   9

Output

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                9

Example 3

Input

      4
     /
    3
   /
  2
 /
1

Output

1
 \
  2
   \
    3
     \
      4

Tags

Binary Search Tree · Recursion · Tree Manipulation · In-order Traversal

---