> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/binary_search_tree/insert-into-a-binary-search-tree.md).

# 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](/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/longest-univalue-path.md))&#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](/project-l/part-1/basic_data_structure/binary_tree/divide_and_conquer/maxmin-depth-of-binary-tree.md)) &#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;


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/binary_search_tree/insert-into-a-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.