Increasing Order Search Tree
Advertisement
Problem
Rearrange the BST so that the leftmost node is the new root and every node has no left child.
Solutions
# Python
def increasingBST(root):
dummy = TreeNode(0)
cur = [dummy]
def inorder(node):
if not node:
return
inorder(node.left)
node.left = None
cur[0].right = node
cur[0] = node
inorder(node.right)
inorder(root)
return dummy.right
// C++
TreeNode* cur;
TreeNode* increasingBST(TreeNode* root) {
TreeNode dummy(0); cur = &dummy;
inorder(root);
return dummy.right;
}
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
node->left = nullptr; cur->right = node; cur = node;
inorder(node->right);
}
// Java
TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0); cur = dummy;
inorder(root);
return dummy.right;
}
void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
node.left = null; cur.right = node; cur = node;
inorder(node.right);
}
// JavaScript
function increasingBST(root) {
const dummy = new TreeNode(0);
let cur = dummy;
function inorder(node) {
if (!node) return;
inorder(node.left);
node.left = null; cur.right = node; cur = node;
inorder(node.right);
}
inorder(root);
return dummy.right;
}
Complexity
- Time: O(n), Space: O(h)
Advertisement
← Previous
Count Nodes Equal to Average of SubtreeNext →
Construct Quad Tree