# Insert into a Binary Search Tree

## Question ([LC.701](https://leetcode.com/problems/insert-into-a-binary-search-tree/)) 

> Given the root of a BST and new value, insert the new value into the BST. 

Assume no duplicated values. 

## Example 

```
I: root at node 2, val = 6


	  2     
	 / \    
	1   4 
	   / 
	  3  


O: root at 2 

	  2     
	 / \    
	1   4 
	   / \
	  3   6 
```

## Analysis 

Traversing the tree then at the base adding the new node is an intuitive solution. 

## Traversing  

```python
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    if root is None:
        return TreeNode(val) 
    
    if val < root.val:
        self.insertHelper(root.left, root, val)
    else:
        self.insertHelper(root.right, root, val)
    
    return root 

def insertHelper(
    self, cur: TreeNode, parent: TreeNode, val: int
) -> None:
    # base 
    
    if cur is None:
        if val < parent.val:
            parent.left = TreeNode(val)
            return
        else:
            parent.right = TreeNode(val)
            return
    
    # recursion 
    if val < cur.val:
        self.insertHelper(cur.left, cur, val)
    else:
        self.insertHelper(cur.right, cur, val)
```

## D\&C&#x20;

Dividing on just one side and merge that one side.&#x20;

```python
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    
    # base 
    if root is None:
        return TreeNode(val)
    
    # divide 
    
    if val < root.val:
        root.left = self.insertIntoBST(root.left, val)
    else:
        root.right = self.insertIntoBST(root.right, val)
    
    return root 
```

Which one is better?&#x20;

* DFS (pre-order traversal) is a little faster in this case because it only has to change the reference of one leaf node. But the time complexity is the same for both at O(h).&#x20;
* D\&C is a lot cleaner to write. This problem requires a special case at the parent level. D\&C can handle that a lot nicer.&#x20;

Is D\&C always a better option?&#x20;

* Traversal only has access to the current node (parent node info has to get passed down). And it can return stuff to the top level.&#x20;
* D\&C has access to the child subtrees because of backtracking.&#x20;
* It is clearly the better option when&#x20;
  * Need information from both subtrees ([Longest Univalue Path](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/longest-univalue-path))&#x20;
  * Want to modify at the parent node level (this problem)&#x20;
* It is a stylistic choice when&#x20;
  * The problem can defined recursively but can also be solved with a global value / log ([Max Depth of Binary Tree](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/maxmin-depth-of-binary-tree)) &#x20;
* It is not preferred when the solution has to be implemented iteratively

Conclusion&#x20;

* When the choice of a design pattern or algorithmic pattern is clear, a clean solution should follow, even when the mind is lack of creativity.&#x20;