Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- 1. Iterative Implementation
- '''
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution:
- def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
- if not root:
- return TreeNode(val)
- curr = root
- while curr:
- prev = curr
- if val <= curr.val:
- curr = curr.left
- else:
- curr = curr.right
- if val <= prev.val:
- prev.left = TreeNode(val)
- else:
- prev.right = TreeNode(val)
- return root
- '''
- 2. Recursive Implementation
- '''
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution:
- def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
- if root is None:
- return TreeNode(val)
- if val < root.val:
- root.left = self.insertIntoBST(root.left, val)
- else:
- root.right = self.insertIntoBST(root.right, val)
- return root
Add Comment
Please, Sign In to add comment