Insert into a Binary Search Tree

Question (LC.701)

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

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

Dividing on just one side and merge that one side.

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?

• 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).

• 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.

Is D&C always a better option?

• 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.

• D&C has access to the child subtrees because of backtracking.

• It is clearly the better option when

  • Need information from both subtrees (Longest Univalue Path)
  • Want to modify at the parent node level (this problem)

• It is a stylistic choice when

  • The problem can defined recursively but can also be solved with a global value / log (Max Depth of Binary Tree)
• It is not preferred when the solution has to be implemented iteratively

Conclusion

• 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.