GoLang: Insert into a Binary Search Tree via Recursion

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:

        4
       / \
      2   7
     / \
    1   3

And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

Insert into BST using GoLang

In GoLang, the syntax to create an object is similar to C/C++. You can use &objectStruct{parameters…}

When it is null root, we new a TreeNode and return otherwise we recursively find out the new value should be inserted into left or right subtree. The new node will be a leaf node which is the simple strategy to insert a new node into a BST despite there are many possible ways to construct a new Binary Search Tree with the given new value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{val, nil, nil}
    }
    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{val, nil, nil}
    }
    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

O(H) time complexity and space complexity where H is the height of the BST.

See other implementations of Inserting into BST:

• Teaching Kids Programming – Insert a Node into a Binary Search Tree via Recursion
• How to Insert into a Binary Search Tree (Recursive and Iterative)?
• GoLang: Insert into a Binary Search Tree via Recursion

–EOF (The Ultimate Computing & Technology Blog) —