Last active
November 8, 2025 06:08
-
-
Save Sedose/1d0ee8a6717feeb28a17aaeb4ff89080 to your computer and use it in GitHub Desktop.
https://leetcode.com/problems/increasing-order-search-tree solution that clearly separates `the logic of tree traversal order` from `the logic of building resulting linked list`
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| fun increasingBST(root: TreeNode?): TreeNode? { | |
| val dummy = TreeNode(0) | |
| var current = dummy | |
| inorder(root) { node -> | |
| node.left = null | |
| current.right = node | |
| current = node | |
| } | |
| return dummy.right | |
| } | |
| private fun inorder(node: TreeNode?, visit: (TreeNode) -> Unit) { | |
| if (node == null) return | |
| inorder(node.left, visit) | |
| visit(node) | |
| inorder(node.right, visit) | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| fun increasingBST(root: TreeNode?): TreeNode? { | |
| val dummy = TreeNode(0) | |
| var tail = dummy | |
| for (node in root.inorder()) { | |
| node.left = null | |
| tail.right = node | |
| tail = node | |
| } | |
| return dummy.right | |
| } | |
| } | |
| private fun TreeNode?.inorder(): Sequence<TreeNode> = | |
| sequence { | |
| if (this@inorder == null) return@sequence | |
| yieldAll(this@inorder.left.inorder()) | |
| yield(this@inorder) | |
| yieldAll(this@inorder.right.inorder()) | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| fun increasingBST(root: TreeNode?): TreeNode? { | |
| val dummy = TreeNode(0) | |
| var current = dummy | |
| for (node in inOrderNodeSequence(root)) { | |
| node.left = null | |
| current.right = node | |
| current = node | |
| } | |
| return dummy.right | |
| } | |
| private fun inOrderNodeSequence(root: TreeNode?): Sequence<TreeNode> = | |
| sequence { | |
| suspend fun SequenceScope<TreeNode>.traverse(node: TreeNode?) { | |
| if (node == null) return | |
| traverse(node.left) | |
| yield(node) | |
| traverse(node.right) | |
| } | |
| traverse(root) | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.stream.Stream; | |
| class Solution { | |
| public TreeNode increasingBST(TreeNode root) { | |
| TreeNode dummy = new TreeNode(0); | |
| TreeNode[] current = { dummy }; | |
| inOrderNodes(root).forEach(next -> { | |
| next.left = null; | |
| current[0].right = next; | |
| current[0] = next; | |
| }); | |
| return dummy.right; | |
| } | |
| private Stream<TreeNode> inOrderNodes(TreeNode node) { | |
| if (node == null) { | |
| return Stream.empty(); | |
| } | |
| return Stream.concat( | |
| Stream.concat( | |
| inOrderNodes(node.left), | |
| Stream.of(node) | |
| ), | |
| inOrderNodes(node.right) | |
| ); | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const increasingBST = | |
| (root) => { | |
| const dummy = new TreeNode(0); | |
| let current = dummy; | |
| for (const next of inOrderNodes(root)) { | |
| next.left = null; | |
| current.right = next; | |
| current = next; | |
| } | |
| return dummy.right; | |
| }; | |
| function* inOrderNodes(node) { | |
| if (!node) return; | |
| yield* inOrderNodes(node.left); | |
| yield node; | |
| yield* inOrderNodes(node.right); | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def increasingBST(self, root: TreeNode) -> TreeNode: | |
| dummy = TreeNode() | |
| current = dummy | |
| for next in in_order_nodes(root): | |
| next.left = None | |
| current.right = next | |
| current = next | |
| return dummy.right | |
| def in_order_nodes(node: TreeNode) -> Generator[TreeNode, None, None]: | |
| if node is None: | |
| return | |
| yield from in_order_nodes(node.left) | |
| yield node | |
| yield from in_order_nodes(node.right) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment