Leetcode # 701. Insert into a Binary Search Tree

https://leetcode.com/problems/insert-into-a-binary-search-tree/

Solution

Time Complexity: O(log(len(tree)))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    head = TreeNode(0, root, None)
    cur = [root, head, 0, 1] # [node, parent, left child or right child, level]
    while cur[0]:
      cur = [cur[0].right, cur[0], 1, cur[3] + 1] if val > cur[0].val \
            else [cur[0].left, cur[0], 0, cur[3] + 1]
    if cur[2] == 0:
      cur[1].left = TreeNode(val)
    else:
      cur[1].right = TreeNode(val)
    return head.left

Last Updated on 2024/06/08 by A1go