Could also use
lgc.left = lgc = root.
No, seriously, my name really is Stefan. Not Stephan, Stephen, Steven or even Stefen.
Posts made by StefanPochmann
RE: Split BST
Time Complexity: O(N), where N is the number of nodes in the input tree, as each node is checked once.
You could also say O(height), right? Your "each node is checked once" sounds so absolute, like that's always the case, not just in worst cases.
And hmm... the Python specification says
rtype: List[TreeNode]and I always understood that as
list. But you don't return a
tuple. Does "
List" mean "any kind of list", not just
list, and does
tuplecount as "
List"? That would at least be non-standard terminology.
Short Python / Ruby
If the root is larger than V, then return it as the greater-than part after extracting the smaller-or-equal part out of its left subtree. Otherwise return it as the smaller-or-equal part after extracting the greater-than part out of its right subtree.
I like directly assigning right back to
root.rightfrom the recursive call. I's not just shorter than using an extra temporary variable, I also find it clearer. I like how it expresses "extract the other part out of this".
def splitBST(self, root, V): if not root: return [None, None] if root.val > V: se, root.left = self.splitBST(root.left, V) return [se, root] root.right, gt = self.splitBST(root.right, V) return [root, gt]
def split_bst(root, v) return [nil, nil] if root.nil? if root.val > v se, root.left = split_bst(root.left, v) [se, root] else root.right, gt = split_bst(root.right, v) [root, gt] end end
Python with internal helper to shorten a few things (no need for
self., no need to pass
V, and shorter function name):
def splitBST(self, root, V): def split(root): if not root: return [None, None] if root.val > V: se, root.left = split(root.left) return [se, root] root.right, gt = split(root.right) return [root, gt] return split(root)