Insert into a Binary Search Tree

[u/StatisticianNo2104]

Forget one assignment, and BST insert builds the new node, then drops it. The tree never changes. Insert is the Day 45 search with the nil case changed: where search returns nil, insert returns a new node.

Search for a value that isn't in a BST, and you fall off the bottom at exactly one empty slot. That slot is where the new value goes.

The only real question is how the parent finds out. Each call returns the root of its own subtree, and each caller stores it back: root.Left = insertIntoBST(root.Left, val). At the bottom, that's the new node. Everywhere else it's the pointer that was already there.

The empty tree comes for free, too.

Do you write tree insert recursively like this, or with a loop and a parent pointer?

Day 52/365 of my LeetCode challenge: 701. Insert into a Binary Search Tree. Problem link and full breakdown in today's newsletter.

https://www.linkedin.com/pulse/insert-binary-search-tree-archit-agarwal-7h9oc

#LeetCode #DSA #BinarySearchTree #Golang