# [Leet Code] Insert into a Binary Search Tree

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

Problem:

You are given the `root`

node of a binary search tree (BST) and a `value`

to insert into the tree. Return *the root node of the BST after the insertion*. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return **any of them**.

**Example 1:**

**Input:** root = [4,2,7,1,3], val = 5

**Output:** [4,2,7,1,3,5]

**Explanation:** Another accepted tree is:

**Example 2:**

**Input:** root = [40,20,60,10,30,50,70], val = 25

**Output:** [40,20,60,10,30,50,70,null,null,25]

**Example 3:**

**Input:** root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

**Output:** [4,2,7,1,3,5]

Solution:

`# Definition for a binary tree node.`

# class TreeNode(object):

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution(object):

def insertIntoBST(self, root, val):

"""

:type root: TreeNode

:type val: int

:rtype: TreeNode

"""

if not root:

return TreeNode(val)

self.traverse(root, val)

return root

def traverse(self, root, val):

if root:

if val > root.val:

if root.right:

self.traverse(root.right, val)

else:

root.right = TreeNode(val)

if val < root.val:

if root.left:

self.traverse(root.left, val)

else:

root.left = TreeNode(val)

Explanation:

First we check for the edge case of if the root node is empty, then we will still need to insert the value that we’ve been given, so we return the value in the TreeNode data type. Then we carry on with normal operations, we create a helper method called traverse, and this takes the same parameters as the main method. We check that root is present, then we check if the value we’ve been given (make sure to note that it’s an int, and our nodes are of format TreeNode, so we need to compare on the root.val which is an integer) is greater than or less than the root node’s value. If it’s greater than, we traverse down the right side of the tree. If it’s less than, we traverse down the left side of the tree. Then we check if there is a left or a right node present after that node, and if there is, continue to traverse, however, if not, then we want to insert our “new node” in here.