Lesson 106 of 250
701. Insert into a Binary Search Tree
NeetCode: Insert into a Binary Search Tree · LeetCode: 701. Insert into a Binary Search Tree · Difficulty: Medium
You are given the root of a binary search tree (BST) and a value val that is not already in the tree. Insert val and return the root of the resulting BST. Any valid result is accepted; the simplest is to attach the value as a new leaf.
Example
Input: [4, 2, 7, 1, 3], val = 5
Output: [4, 2, 7, 1, 3, 5] (5 becomes the left child of 7)
4 4
/ \ / \
2 7 -> 2 7
/ \ / \ /
1 3 1 3 5
Input: [], val = 5 -> a single node 5The programs below print the inorder listing of the result, which must be the sorted values including val. Only the optimal one also prints the exact shape (preorder with N for missing children).
Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.
Brute force: rebuild from a sorted list
Read the tree out in order (which gives a sorted List<Integer>), insert val at its sorted position, and build a fresh balanced BST from the list by repeatedly taking the middle element as the root.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
List<Integer> values = new ArrayList<>();
Main.inorder(root, values);
int pos = 0;
while (pos < values.size() && values.get(pos) < val) pos++;
values.add(pos, val);
return build(values, 0, values.size());
}
// Builds a balanced BST from sorted.subList(lo, hi) by taking the middle as the root.
private TreeNode build(List<Integer> sorted, int lo, int hi) {
if (lo >= hi) return null;
int mid = lo + (hi - lo) / 2;
TreeNode node = new TreeNode(sorted.get(mid));
node.left = build(sorted, lo, mid);
node.right = build(sorted, mid + 1, hi);
return node;
}
}
public class Main {
/** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
static TreeNode tree(Integer... values) {
if (values.length == 0 || values[0] == null) return null;
TreeNode root = new TreeNode(values[0]);
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty() && i < values.length) {
TreeNode node = queue.poll();
if (i < values.length && values[i] != null) {
node.left = new TreeNode(values[i]);
queue.add(node.left);
}
i++;
if (i < values.length && values[i] != null) {
node.right = new TreeNode(values[i]);
queue.add(node.right);
}
i++;
}
return root;
}
static void inorder(TreeNode node, List<Integer> out) {
if (node == null) return;
inorder(node.left, out);
out.add(node.val);
inorder(node.right, out);
}
static void show(TreeNode root, int val) {
TreeNode result = new Solution().insertIntoBST(root, val);
List<Integer> out = new ArrayList<>();
inorder(result, out);
System.out.println(out);
}
public static void main(String[] args) {
show(tree(4, 2, 7, 1, 3), 5);
show(tree(), 5);
show(tree(40, 20, 60, 10, 30, 50, 70), 25);
}
}[1, 2, 3, 4, 5, 7]
[5]
[10, 20, 25, 30, 40, 50, 60, 70]Correct, but it touches every node and throws away the existing structure (it also allocates a whole new tree) to add one value. values.add(pos, val) shifts the elements after pos, which is O(n) as well. Time: O(n). Space: O(n).
Optimal: walk down one path and attach a leaf
The BST property tells you exactly where the value belongs: go left if val is smaller than the current node, right otherwise, until you reach an empty slot, and put the new node there. Only one root-to-leaf path is touched. The loop keeps the node it is standing on. When the next step would move to a null child, it assigns the new node to that child field and stops. An empty tree is the one case with no node to stand on, so the new node itself is returned.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode fresh = new TreeNode(val);
if (root == null) return fresh;
TreeNode cur = root;
while (true) {
if (val < cur.val) {
if (cur.left == null) {
cur.left = fresh;
return root;
}
cur = cur.left;
} else {
if (cur.right == null) {
cur.right = fresh;
return root;
}
cur = cur.right;
}
}
}
}
public class Main {
/** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
static TreeNode tree(Integer... values) {
if (values.length == 0 || values[0] == null) return null;
TreeNode root = new TreeNode(values[0]);
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty() && i < values.length) {
TreeNode node = queue.poll();
if (i < values.length && values[i] != null) {
node.left = new TreeNode(values[i]);
queue.add(node.left);
}
i++;
if (i < values.length && values[i] != null) {
node.right = new TreeNode(values[i]);
queue.add(node.right);
}
i++;
}
return root;
}
/** Preorder listing with N for a missing child. */
static String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeInto(root, sb);
return sb.toString();
}
static void serializeInto(TreeNode node, StringBuilder sb) {
if (sb.length() > 0) sb.append(',');
if (node == null) {
sb.append('N');
return;
}
sb.append(node.val);
serializeInto(node.left, sb);
serializeInto(node.right, sb);
}
static void inorder(TreeNode node, List<Integer> out) {
if (node == null) return;
inorder(node.left, out);
out.add(node.val);
inorder(node.right, out);
}
static void show(TreeNode root, int val) {
TreeNode result = new Solution().insertIntoBST(root, val);
List<Integer> out = new ArrayList<>();
inorder(result, out);
System.out.println(out + " shape: " + serialize(result));
}
public static void main(String[] args) {
show(tree(4, 2, 7, 1, 3), 5);
show(tree(), 5);
show(tree(40, 20, 60, 10, 30, 50, 70), 25);
}
}[1, 2, 3, 4, 5, 7] shape: 4,2,1,N,N,3,N,N,7,5,N,N,N
[5] shape: 5,N,N
[10, 20, 25, 30, 40, 50, 60, 70] shape: 40,20,10,N,N,30,25,N,N,N,60,50,N,N,70,N,NThe tree can become unbalanced (inserting sorted values builds a chain), so the cost is proportional to the height, which is O(log n) for a balanced tree and O(n) in the worst case. Time: O(h). Space: O(1) extra, since the loop is iterative.