now you have a working golang example…
package main
import (
“bufio”
“fmt”
“os”
“strconv”
“strings”
)
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
serTree=dfsSer(tree)
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]
*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)
scanner.Scan()
rootIdx := 0
root := buildTree(splitWords(scanner.Text()), &rootIdx)
scanner.Scan()
value,_ := strconv.Atoi(scanner.Text())
res := insertBst(root,value)
out :=ser(res)
fmt.Println(out)
}
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
Solution+Node`1[System.Int32]
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
else:
return bst
if val < parent.val:
parent.left = Node(val)
else:
parent.right = Node(val)
For C#, the last line in Main() should be:
Console.WriteLine(String.Join(' ', resArr));
Not
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
else:
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