Leetcode

Insert into a Binary Search Tree

May 26, 2022 by aAshish

  • Time:O(\log n) \to O(n)
  • Space:O(\log n) \to O(n)

C++

 
class Solution {
 public:
  TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root)
      return new TreeNode(val);
    if (root->val > val)
      root->left = insertIntoBST(root->left, val);
    else
      root->right = insertIntoBST(root->right, val);
    return root;
  }
};

JAVA

 
class Solution {
  public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null)
      return new TreeNode(val);
    if (root.val > val)
      root.left = insertIntoBST(root.left, val);
    else
      root.right = insertIntoBST(root.right, val);
    return root;
  }
}

Python

 
class Solution:
  def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root:
      return TreeNode(val)
    if root.val > val:
      root.left = self.insertIntoBST(root.left, val)
    else:
      root.right = self.insertIntoBST(root.right, val)
    return root