# 701. Insert into a Binary Search Tree
LeetCode Problem Link (opens new window)
Given the root node of a binary search tree (BST) and a value to insert into the tree, insert the value into the binary search tree. Return the root node of the binary search tree after the insertion. It is guaranteed that the new value and the original binary search tree's node values are different from each other.
Note that there may be multiple valid ways to insert the value, as long as the tree remains a binary search tree after insertion. You can return any of them.
Constraints:
- The number of nodes in the given tree is between 0 and 10^4.
- Each node has a unique integer value, ranging from 0 to 10^8.
- -10^8 <= val <= 10^8
- The new value and node values in the original BST are different.
# Solution
This problem is actually quite simple, but the hint in the problem stating that there are multiple valid insertion methods, and that the structure of the binary search tree can be changed, can be intimidating. However, it is not necessary to consider the hinted changes to the tree structure.
Following the video demonstration, you can see: as long as you traverse according to the rules of the binary search tree and insert the node when encountering a null position, you're good to go.
For example, inserting the element 10 requires finding the end node to insert. The same can be applied to inserting elements 15, 0, and 6. Do you need to adjust the structure of the binary tree? Not necessary.
Simply traverse the binary search tree, find a null node, and insert the element. With that, the problem becomes simple.
Next is the process of traversing the binary search tree.
# Recursion
Recursion consists of three steps:
- Determine the parameters and return value of the recursion function.
The parameters just need to be the root node pointer and the element to insert. Should the recursive function have a return value?
It can have one or not, but implementing it without a return value can be cumbersome, as shown in the code provided below.
With a return value, you can use it to complete the assignment of a new node to its parent.
The return type of the recursive function is the node type TreeNode *.
Code:
TreeNode* insertIntoBST(TreeNode* root, int val)
- Set termination conditions
The termination condition is to find a null node, which is the position to insert the new node, and return the inserted node.
Code:
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
2
3
4
By returning the added node to the previous level, the assignment between parent and child nodes is complete, which will be explained further.
- Define the logic of a single recursion level
At this point, you need to make it clear whether you need to traverse the entire tree?
Don't forget this is a search tree, traversing the entire search tree defeats its purpose.
Search trees have a direction, you can decide the direction of recursion according to the value of the element to insert.
Code:
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
2
3
Here, you should be able to sense how through the return value of the recursive function the labelling of new nodes with their parent is accomplished; the next level returns the newly added node, and the current level uses root->left or root->right to catch it.
Here is the complete code:
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
2
3
4
5
6
7
8
9
10
11
12
The code is not complicated.
As mentioned earlier, it's possible to not have a return value in the recursive function. You just need to find the insertion position and let the parent node point to the inserted node, then end the recursion.
In this case, define the recursive function as follows:
TreeNode* parent; // Record the parent node of the current node
void traversal(TreeNode* cur, int val)
2
Without a return value, you need to record the previous node (parent). When you encounter a null node, let the parent's left or right child point to the new inserted node, then end the recursion.
Code:
class Solution {
private:
TreeNode* parent;
void traversal(TreeNode* cur, int val) {
if (cur == NULL) {
TreeNode* node = new TreeNode(val);
if (val > parent->val) parent->right = node;
else parent->left = node;
return;
}
parent = cur;
if (cur->val > val) traversal(cur->left, val);
if (cur->val < val) traversal(cur->right, val);
return;
}
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
parent = new TreeNode(0);
if (root == NULL) {
root = new TreeNode(val);
}
traversal(root, val);
return root;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
It's a bit more cumbersome.
I gave this example to show that completing the assignment of new nodes and their parent nodes using the return value of the recursive function can bring convenience.
The numerous code examples online may mislead everyone into thinking that returning a node through a recursive function is justified, whereas this is actually an optimization!
# Iteration
Let's look at the iterative method. If unfamiliar with writing iterations for binary search trees, refer to: 0700.Search in a Binary Search Tree (opens new window).
During iteration across the binary search tree, it is necessary to record the current node's parent node to accomplish the node insert operation.
Techniques were used to record pre and cur pointers in both 0530.Minimum Absolute Difference in BST (opens new window) and 0501.Find Mode in Binary Search Tree (opens new window). It’s the same in this case.
Code:
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
TreeNode* cur = root;
TreeNode* parent = root; // Important, needs to record the previous node, otherwise, you can't assign the new node.
while (cur != NULL) {
parent = cur;
if (cur->val > val) cur = cur->left;
else cur = cur->right;
}
TreeNode* node = new TreeNode(val);
if (val < parent->val) parent->left = node; // At this point, parent node is used for assignment
else parent->right = node;
return root;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Summary
First of all, there's no need to be intimidated by the restructuring of the search tree in the insertion operation of the binary search tree. In fact, no reconstruction is needed.
In the recursion section, we focused on how to use the return value of the recursion function to complete the assignment between the newly added node and its parent, emphasizing the structured orderliness of the search tree.
Finally, the iterative approach is also provided. The iterative approach requires recording the parent node of the current traversed node, which aligns with the code logic in a recursion function without a return value.
# Other Language Versions
# Java
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
TreeNode newRoot = root;
TreeNode pre = root;
while (root != null) {
pre = root;
if (root.val > val) {
root = root.left;
} else if (root.val < val) {
root = root.right;
}
}
if (pre.val > val) {
pre.left = new TreeNode(val);
} else {
pre.right = new TreeNode(val);
}
return newRoot;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Recursive method
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) // If the current node is null, it means that `val` has found a proper placement. Create the node and return.
return new TreeNode(val);
if (root.val < val){
root.right = insertIntoBST(root.right, val); // Recursively create the right subtree
}else if (root.val > val){
root.left = insertIntoBST(root.left, val); // Recursively create the left subtree
}
return root;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# Python
Recursive method (version 1)
class Solution:
def __init__(self):
self.parent = None
def traversal(self, cur, val):
if cur is None:
node = TreeNode(val)
if val > self.parent.val:
self.parent.right = node
else:
self.parent.left = node
return
self.parent = cur
if cur.val > val:
self.traversal(cur.left, val)
if cur.val < val:
self.traversal(cur.right, val)
def insertIntoBST(self, root, val):
self.parent = TreeNode(0)
if root is None:
return TreeNode(val)
self.traversal(root, val)
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Recursive method (version 2)
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None or root.val == val:
return TreeNode(val)
elif root.val > val:
if root.left is None:
root.left = TreeNode(val)
else:
self.insertIntoBST(root.left, val)
elif root.val < val:
if root.right is None:
root.right = TreeNode(val)
else:
self.insertIntoBST(root.right, val)
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Recursive method (version 3)
class Solution:
def insertIntoBST(self, root, val):
if root is None:
node = TreeNode(val)
return node
if root.val > val:
root.left = self.insertIntoBST(root.left, val)
if root.val < val:
root.right = self.insertIntoBST(root.right, val)
return root
2
3
4
5
6
7
8
9
10
11
12
Iterative method (version 1)
class Solution:
def insertIntoBST(self, root, val):
if root is None: # If the root is null, create a new node as the root and return
node = TreeNode(val)
return node
cur = root
parent = root # Record the previous node for connecting new node
while cur is not None:
parent = cur
if cur.val > val:
cur = cur.left
else:
cur = cur.right
node = TreeNode(val)
if val < parent.val:
parent.left = node # Connect new node to the parent's left subtree
else:
parent.right = node # Connect new node to the parent's right subtree
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Iterative method (version 2)
class Solution:
def insertIntoBST(self, root, val):
if root is None:
return TreeNode(val)
parent = None
cur = root
while cur:
parent = cur
if val < cur.val:
cur = cur.left
else:
cur = cur.right
if val < parent.val:
parent.left = TreeNode(val)
else:
parent.right = TreeNode(val)
return root
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Simplified Iterative method
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root: # If the root is null, create a new node as the root and return
return TreeNode(val)
cur = root
while cur:
if val < cur.val:
if not cur.left: # If at this point the parent's left subtree is null
cur.left = TreeNode(val) # Connect new node to the parent's left subtree
return root
else:
cur = cur.left
elif val > cur.val:
if not cur.right: # If at this point the parent's right subtree is null
cur.right = TreeNode(val) # Connect new node to the parent's right subtree
return root
else:
cur = cur.right
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Go
Recursive method
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
root = &TreeNode{Val: val}
return root
}
if root.Val > val {
root.Left = insertIntoBST(root.Left, val)
} else {
root.Right = insertIntoBST(root.Right, val)
}
return root
}
2
3
4
5
6
7
8
9
10
11
12
Iterative method
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val:val}
}
node := root
var pnode *TreeNode
for node != nil {
if val > node.Val {
pnode = node
node = node.Right
} else {
pnode = node
node = node.Left
}
}
if val > pnode.Val {
pnode.Right = &TreeNode{Val: val}
} else {
pnode.Left = &TreeNode{Val: val}
}
return root
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# JavaScript
Recursive method with return value
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoBST = function (root, val) {
const setInOrder = (root, val) => {
if (root === null) {
let node = new TreeNode(val);
return node;
}
if (root.val > val)
root.left = setInOrder(root.left, val);
else if (root.val < val)
root.right = setInOrder(root.right, val);
return root;
}
return setInOrder(root, val);
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Recursive method without return value
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoBST = function (root, val) {
let parent = new TreeNode(0);
const preOrder = (cur, val) => {
if (cur === null) {
let node = new TreeNode(val);
if (parent.val > val)
parent.left = node;
else
parent.right = node;
return;
}
parent = cur;
if (cur.val > val)
preOrder(cur.left, val);
if (cur.val < val)
preOrder(cur.right, val);
}
if (root === null)
root = new TreeNode(val);
preOrder(root, val);
return root;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Iterative method
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoBST = function (root, val) {
if (root === null) {
root = new TreeNode(val);
} else {
let parent = new TreeNode(0);
let cur = root;
while (cur) {
parent = cur;
if (cur.val > val)
cur = cur.left;
else
cur = cur.right;
}
let node = new TreeNode(val);
if (parent.val > val)
parent.left = node;
else
parent.right = node;
}
return root;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# TypeScript
Recursive - with return value
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null) return new TreeNode(val);
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
};
2
3
4
5
6
7
8
9
Recursive - without return value
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null) return new TreeNode(val);
function recur(root: TreeNode | null, val: number) {
if (root === null) {
if (parentNode.val > val) {
parentNode.left = new TreeNode(val);
} else {
parentNode.right = new TreeNode(val);
}
return;
}
parentNode = root;
if (root.val > val) recur(root.left, val);
if (root.val < val) recur(root.right, val);
}
let parentNode: TreeNode = root;
recur(root, val);
return root;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Iterative method
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
if (root === null) return new TreeNode(val);
let curNode: TreeNode | null = root;
let parentNode: TreeNode = root;
while (curNode !== null) {
parentNode = curNode;
if (curNode.val > val) {
curNode = curNode.left
} else {
curNode = curNode.right;
}
}
if (parentNode.val > val) {
parentNode.left = new TreeNode(val);
} else {
parentNode.right = new TreeNode(val);
}
return root;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Scala
Recursive:
object Solution {
def insertIntoBST(root: TreeNode, `val`: Int): TreeNode = {
if (root == null) return new TreeNode(`val`)
if (`val` < root.value) root.left = insertIntoBST(root.left, `val`)
else root.right = insertIntoBST(root.right, `val`)
root // Return the root node
}
}
2
3
4
5
6
7
8
Iterative:
object Solution {
def insertIntoBST(root: TreeNode, `val`: Int): TreeNode = {
if (root == null) {
return new TreeNode(`val`)
}
var parent = root // Record current node's parent
var curNode = root
while (curNode != null) {
parent = curNode
if(`val` < curNode.value) curNode = curNode.left
else curNode = curNode.right
}
if(`val` < parent.value) parent.left = new TreeNode(`val`)
else parent.right = new TreeNode(`val`)
root // Finally, return the root node
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Rust
Iterative:
impl Solution {
pub fn insert_into_bst(
root: Option<Rc<RefCell<TreeNode>>>,
val: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_none() {
return Some(Rc::new(RefCell::new(TreeNode::new(val))));
}
let mut cur = root.clone();
let mut pre = None;
while let Some(node) = cur.clone() {
pre = cur;
if node.borrow().val > val {
cur = node.borrow().left.clone();
} else {
cur = node.borrow().right.clone();
};
}
let r = Some(Rc::new(RefCell::new(TreeNode::new(val))));
let mut p = pre.as_ref().unwrap().borrow_mut();
if val < p.val {
p.left = r;
} else {
p.right = r;
}
root
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Recursive:
impl Solution {
pub fn insert_into_bst(
root: Option<Rc<RefCell<TreeNode>>>,
val: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = &root {
if node.borrow().val > val {
let left = Self::insert_into_bst(node.borrow_mut().left.take(), val);
node.borrow_mut().left = left;
} else {
let right = Self::insert_into_bst(node.borrow_mut().right.take(), val);
node.borrow_mut().right = right;
}
root
} else {
Some(Rc::new(RefCell::new(TreeNode::new(val))))
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# C#
Recursive
public TreeNode InsertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (root.val > val) root.left = InsertIntoBST(root.left, val);
if (root.val < val) root.right = InsertIntoBST(root.right, val);
return root;
}
2
3
4
5
6
7