Insert Into BST - Depth First Search / Binary Search Tree

now you have a working golang example…

package main

import (

type Node struct {
val int
left *Node
right *Node

func insertBst(root *Node,value int) *Node {

if root == nil {
	root = &Node{value,nil,nil}
	return root
return dfs(root,value)


func dfs(tree *Node,value int) *Node {

if tree.val == value {
	return tree //value already exists
switch value > tree.val {
case true :                 // we look to the right
	if tree.right == nil { // if this is a leaf node we can add the new node here
		tree.right = &Node{value,nil,nil}
		return tree
	} else {dfs(tree.right,value)}
case false :               // salvation is on the left 8-)
	if tree.left == nil {
		tree.left = &Node{value,nil,nil}
		return tree
	} else {dfs(tree.left,value)}
return tree


func ser(tree *Node) string {

var serTree string
return serTree

func dfsSer(tree *Node) string {

if tree == nil {
	return "x "
return fmt.Sprintf("%d ",tree.val) + dfsSer(tree.left) + dfsSer(tree.right)


func buildTree(nodes []string, pos *int) *Node {
val := nodes[*pos]
if val == “x” {
return nil
v, _ := strconv.Atoi(val)
left := buildTree(nodes, pos)
right := buildTree(nodes, pos)
return &Node{v, left, right}

func splitWords(s string) []string {
if s == “” {
return []string{}
return strings.Split(s, " ")

func main() {
scanner := bufio.NewScanner(os.Stdin)
rootIdx := 0
root := buildTree(splitWords(scanner.Text()), &rootIdx)
value,_ := strconv.Atoi(scanner.Text())
res := insertBst(root,value)
out :=ser(res)

Yup - they consistently have completely missing or (even worse IMO) incorrect golang code. At least if it’s missing I’m not pulling my hair trying to figure out why MY code isn’t working.

Can you add the array representation of the BST used in the Explanation?

you can see it by in ‘Custom Input’
8 4 2 1 x x 3 x x 6 x x 12 10 x x 14 x 15 x x

The base C# code fails to compile. Can someone fix it please? Thanks.

Yes, line 67 Add method start with capital letter.
But anyway there is smth wrong with test check. It just call ToString on result which in case of Node just type name and can’t compare it with string representation of a tree.
Your Output
Expected Output
8 4 2 1 x x 3 x x 6 x 7 x x 12 10 x x 14 x 15 x x

might be good to provide iterative approaches/solutions as well

here is mine:

def insert_bst(bst: Node, val: int) → Node:
if not bst:
return Node(val)

curr = parent = bst
while curr:
    parent = curr
    if val < curr.val:
        curr = curr.left
    elif val > curr.val:
        curr = curr.right
        return bst

if val < parent.val:
    parent.left = Node(val)
    parent.right = Node(val)

For C#, the last line in Main() should be:
Console.WriteLine(String.Join(' ', resArr));

Console.WriteLine(String.Join(' ', res));

Can someone explain why this doesnt work?

function insertBst(bst, val) {
if(!root) return new TreeNode(val)

if(val < root.val) root.left = insertBst(root.left,val)
else root.right = insertBst(root.right,val)

return root


Hi cdr,

You need an “else if” instead of an “else” so that the val == root.val case falls through to the return statement.

the problem ask to return the whole BST, so your code only return undefine since ELSE in your code

Structured Programming JS Solution:

function insertBst(bst, val) {
    let result = bst;
    if (result) {
        if (result.val < val) {
            result.right = insertBst(result.right, val);
        } else if (result.val > val) {
            result.left = insertBst(result.left, val);
    } else {
        result = new Node(val);
    return result;

why return bst

the question asks us to return “a valid BST with the inserted number, or the same BST if the number already exist”

This process that AlgoMonster tries to teach us is so infuriating, they flip flop between ways to create solutions. Sometimes we have a helper function sometimes we don’t. Sometimes we utilize a state for example in the BST section and sometimes we don’t.

This answer uses previous idea of ‘search range’ to traverse
but it doesn’t make use of the nature of binary search.
So this is an O(n) approach.
The standard answer is much simpler with O(log(n))

def insert_bst(bst: Node, val: int) -> Node:
    parent_node = None
    def dfs(node, val, min_val, max_val, is_left, parent_node=None):
        if node is None:
            if min_val < val < max_val:
                node = Node(val)
                if is_left:
                    parent_node.left = node
                    parent_node.right = node
                return True
            return False
        if node.val == val:
            return True
        inserted = dfs(node.left, val, min_val, node.val, True, node)
        if inserted:
            return True
        inserted = dfs(node.right, val, node.val, node.right, False, node)
        if inserted:
            return True
        return False
    dfs(bst, val, -float("inf"), float("inf"), None)
    return bst