Repository navigation
Expand file tree
/
Copy pathinsertIntoBinarySearchTree.js
More file actions
67 lines (58 loc) · 1.78 KB
/
Copy pathinsertIntoBinarySearchTree.js
File metadata and controls
67 lines (58 loc) · 1.78 KB
1
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
You are given the root node of a binary search tree (BST) and a value to insert
into the tree. Return the root node of the BST after the insertion. It is
guaranteed that the new value does not exist in the original BST.
Notice 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.
* 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}
*/
//while loop
function insertIntoBST(root, val) {
let newNode = new TreeNode(val);
if (!root) {
root = newNode;
return root;
}
let curNode = root;
while (curNode !== null) {
console.log('curNode', curNode)
if (val < curNode.val) {
if (curNode.left === null) {
curNode.left = newNode;
return root;
} else {
//Go deeper
curNode = curNode.left;
}
}
if (val > curNode.val) {
if (curNode.right === null) {
curNode.right = newNode;
return root;
} else {
curNode = curNode.right;
}
}
}
}
//recursion
function insertIntoBST(root, val) {
if (root === null) {
root = new TreeNode(val);
//insert to the left subtree
} else if (val < root.val) {
root.left = insertIntoBST(root.left, val);
//insert to the right subtree
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root
}