Skip to content

Commit 1667437

Browse files
BarklimBarklim
Barklim
authored and
Barklim
committed
fix test cases for binary trees
1 parent b144fc3 commit 1667437

15 files changed

+260
-71
lines changed

‎0098-validate-binary-search-tree.js

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,3 +38,23 @@ function traverse(root, min, max) {
3838

3939
return traverse(root.left, min, root.val) && traverse(root.right, root.val, max);
4040
}
41+
42+
// function isValidBST(root) {
43+
// if (!root) return true;
44+
45+
// let stack = [[root, -Infinity, Infinity]];
46+
47+
// while (stack.length) {
48+
// let [node, minR, maxR] = stack.pop();
49+
// if (!node) continue;
50+
51+
// if (node.val <= minR || node.val >= maxR) {
52+
// return false;
53+
// }
54+
55+
// stack.push([node.left, minR, node.val]);
56+
// stack.push([node.right, node.val, maxR]);
57+
// }
58+
59+
// return true;
60+
// }

‎0101-symmetric-tree.js

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,3 +32,26 @@ function isBalanced(a, b) {
3232
}
3333
return a.val === b.val && isBalanced(a.left, b.right) && isBalanced(a.right, b.left);
3434
}
35+
36+
// Top solver not working
37+
// function isSymmetric(root) {
38+
// if (!root) return true;
39+
40+
// let stack = [root.left, root.right];
41+
42+
// while (stack.length) {
43+
// let right = stack.pop();
44+
// let left = stack.pop();
45+
46+
// if (!left && !right) continue;
47+
// if (!left || !right) return false;
48+
// if (left.val !== right.val) return false;
49+
50+
// stack.push(left.left);
51+
// stack.push(right.right);
52+
// stack.push(left.right);
53+
// stack.push(right.left);
54+
// }
55+
56+
// return true;
57+
// }

‎0102-binary-tree-level-order-traversal.js

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,3 +38,28 @@ function traverse(result, node, level = 0) {
3838
traverse(result, node.left, level + 1);
3939
traverse(result, node.right, level + 1);
4040
}
41+
42+
// function levelOrder(root) {
43+
// if (!root) return [];
44+
45+
// let result = [];
46+
// let queue = [root];
47+
48+
// while (queue.length) {
49+
// let levelSize = queue.length;
50+
// let currentLevel = [];
51+
52+
// for (let i = 0; i < levelSize; i++) {
53+
// let node = queue.shift();
54+
// currentLevel.push(node.val);
55+
56+
// if (node.left) queue.push(node.left);
57+
// if (node.right) queue.push(node.right);
58+
// }
59+
60+
// result.push(currentLevel);
61+
// }
62+
63+
// return result;
64+
// }
65+

‎0110-balanced-binary-tree.js

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,3 +28,20 @@ function traverse(node, depth = 0) {
2828
if (!node) return depth;
2929
return Math.max(traverse(node.right, depth + 1), traverse(node.left, depth + 1));
3030
}
31+
32+
// function isBalanced(root) {
33+
// function height(node) {
34+
// if (!node) return 0;
35+
// return 1 + Math.max(height(node.left), height(node.right));
36+
// }
37+
38+
// if (!root) return true;
39+
40+
// let leftH = height(root.left);
41+
// let rightH = height(root.right);
42+
43+
// if (Math.abs(leftH - rightH) > 1) return false;
44+
45+
// return isBalanced(root.left) && isBalanced(root.right);
46+
// }
47+

‎0112-path-sum.js

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,3 +42,25 @@ function traverse(result, node, sum = 0) {
4242
if (node.left) traverse(result, node.left, sum + node.val);
4343
if (node.right) traverse(result, node.right, sum + node.val);
4444
}
45+
46+
// function hasPathSum(root, targetSum) {
47+
// if (!root) return false;
48+
49+
// let stack = [[root, 0]];
50+
51+
// while (stack.length) {
52+
// let [node, currentSum] = stack.pop();
53+
// if (!node) continue;
54+
55+
// currentSum += node.val;
56+
57+
// if (!node.left && !node.right && currentSum === targetSum) {
58+
// return true;
59+
// }
60+
61+
// stack.push([node.left, currentSum]);
62+
// stack.push([node.right, currentSum]);
63+
// }
64+
65+
// return false;
66+
// }

‎0700-search-in-a-binary-search-tree.js

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,3 +32,6 @@ var searchBST = function(root, val) {
3232

3333
return null;
3434
};
35+
36+
// Or recursive
37+
// searchBST(root.left, val)

‎dStructure/binTree.js

Lines changed: 45 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
class TreeNode {
2-
constructor(value) {
3-
this.value = value;
2+
constructor(val) {
3+
this.val = val;
44
this.left = null;
55
this.right = null
66
}
@@ -11,8 +11,8 @@ class BinaryTree {
1111
this.root = null;
1212
}
1313

14-
add(value) {
15-
const newNode = new TreeNode(value)
14+
add(val) {
15+
const newNode = new TreeNode(val)
1616
if (!this.root) {
1717
this.root = newNode;
1818
return;
@@ -21,7 +21,7 @@ class BinaryTree {
2121
let currentNode = this.root;
2222

2323
while(currentNode) {
24-
if (newNode.value < currentNode.value) {
24+
if (newNode.val < currentNode.val) {
2525
if (!currentNode.left) {
2626
currentNode.left = newNode;
2727
return;
@@ -40,13 +40,13 @@ class BinaryTree {
4040
}
4141
}
4242

43-
search(value) {
43+
search(val) {
4444
let currentNode = this.root;
4545
while (currentNode) {
46-
if (value === currentNode.value) {
46+
if (val === currentNode.val) {
4747
return currentNode;
4848
}
49-
if (value < currentNode.value) {
49+
if (val < currentNode.val) {
5050
currentNode = currentNode.left;
5151
} else {
5252
currentNode = currentNode.right;
@@ -57,7 +57,7 @@ class BinaryTree {
5757

5858
print(root = this.root) {
5959
if (!root) return true
60-
console.log(root.value)
60+
console.log(root.val)
6161
this.print(root.left)
6262
this.print(root.right)
6363
}
@@ -89,15 +89,40 @@ function createTreeFromArray(arr) {
8989
return root;
9090
}
9191

92-
const myTree = new BinaryTree();
93-
const treeFromArray = createTreeFromArray([3,9,20,null,null,15,7]);
94-
var myTreeStringify = JSON.stringify(treeFromArray, null, 2);
92+
var levelOrder = function(root) {
93+
if (!root) return [];
9594

96-
const foundNode = myTree.search(10);
97-
98-
console.log('!!! myTree');
99-
// console.log(myTree);
100-
// console.log(myTree.print());
101-
console.log(myTreeStringify);
102-
// console.log(foundNode);
103-
console.log('!!!');
95+
let result = [];
96+
let queue = [root];
97+
98+
while (queue.length) {
99+
let levelSize = queue.length;
100+
let currentLevel = [];
101+
102+
for (let i = 0; i < levelSize; i++) {
103+
let node = queue.shift();
104+
currentLevel.push(node.val);
105+
106+
if (node.left) queue.push(node.left);
107+
if (node.right) queue.push(node.right);
108+
}
109+
110+
result.push(currentLevel);
111+
}
112+
113+
return result;
114+
};
115+
116+
// const myTree = new BinaryTree();
117+
// const treeFromArray = createTreeFromArray([3,9,20,null,null,15,7]);
118+
// var myTreeStringify = JSON.stringify(treeFromArray, null, 2);
119+
120+
// const foundNode = myTree.search(10);
121+
122+
// console.log('!!! myTree');
123+
// // console.log(myTree);
124+
// // console.log(myTree.print());
125+
// console.log(myTreeStringify);
126+
// // console.log(foundNode);
127+
// // levelOrder(createTreeFromArray([3,9,20,null,null,15,7]))
128+
// console.log('!!!');

‎example/6.Tree/0098.js

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -14,10 +14,12 @@ var isValidBST = function(root) {
1414

1515
};
1616

17-
const example1 = isValidBST(); // root = [2,1,3] // true
18-
const example2 = isValidBST(); // root = [5,1,4,null,null,3,6] // false
19-
const example3 = isValidBST(); // root = [1,2,3] // false
17+
const testCases = [
18+
{ input: [2,1,3], expected: true },
19+
{ input: [5,1,4,null,null,3,6], expected: false },
20+
{ input: [1,2,3], expected: false },
21+
{ input: [] , expected: true },
22+
];
2023

21-
console.log(example1);
22-
console.log(example2);
23-
console.log(example3);
24+
const results = testCases.map(({ input }) => isValidBST(createTreeFromArray(input)));
25+
console.log(results);

‎example/6.Tree/0101.js

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -14,12 +14,12 @@ var isSymmetric = function(root) {
1414

1515
};
1616

17-
const example1 = isSymmetric(); // [1,2,2,3,4,4,3] // true
18-
const example2 = isSymmetric(); // [1,2,2,null,3,null,3] // false
19-
const example3 = isSymmetric(); // [1,2,3,null,null,4] // 3
20-
const example4 = isSymmetric(); // [] // 0
17+
const testCases = [
18+
{ input: [1,2,2,3,4,4,3], expected: true },
19+
{ input: [1,2,2,null,3,null,3], expected: false },
20+
{ input: [1,2,3,null,null,4], expected: false },
21+
{ input: [] , expected: true },
22+
];
2123

22-
console.log(example1);
23-
console.log(example2);
24-
console.log(example3);
25-
console.log(example4);
24+
const results = testCases.map(({ input }) => isSymmetric(createTreeFromArray(input)));
25+
console.log(results);

‎example/6.Tree/0102.js

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -11,15 +11,15 @@
1111
* @return {number[][]}
1212
*/
1313
var levelOrder = function(root) {
14-
14+
1515
};
1616

17-
const example1 = levelOrder(); // root = [3,9,20,null,null,15,7] // [[3],[9,20],[15,7]]
18-
const example2 = levelOrder(); // root = [1] // [[1]]
19-
const example3 = levelOrder(); // root = [] // []
20-
const example4 = levelOrder(); // root = [1,2,3,4,5,6,7] // [[1],[2,3],[4,5,6,7]]
17+
const testCases = [
18+
{ input: [3,9,20,null,null,15,7], expected: [[3],[9,20],[15,7]] },
19+
{ input: [1], expected: [[1]] },
20+
{ input: [] , expected: [] },
21+
{ input: [1,2,3,4,5,6,7], expected: [[1],[2,3],[4,5,6,7]] }
22+
];
2123

22-
console.log(example1);
23-
console.log(example2);
24-
console.log(example3);
25-
console.log(example4);
24+
const results = testCases.map(({ input }) => levelOrder(createTreeFromArray(input)));
25+
console.log(results);

‎example/6.Tree/0110.js

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -14,14 +14,13 @@ var isBalanced = function(root) {
1414

1515
};
1616

17-
const example1 = isBalanced(); // root = [3,9,20,null,null,15,7] // true
18-
const example2 = isBalanced(); // root = [1,2,2,3,3,null,null,4,4] // false
19-
const example3 = isBalanced(); // root = [] // true
20-
const example4 = isBalanced(); // root = [1,2,3,null,null,4] // true
21-
const example5 = isBalanced(); // root = [1,2,3,null,null,4,null,5] // false
17+
const testCases = [
18+
{ input: [3,9,20,null,null,15,7], expected: true },
19+
{ input: [1,2,2,3,3,null,null,4,4], expected: false },
20+
{ input: [] , expected: true },
21+
{ input: [1,2,3,null,null,4], expected: true },
22+
{ input: [1,2,3,null,null,4,null,5], expected: false }
23+
];
2224

23-
console.log(example1);
24-
console.log(example2);
25-
console.log(example3);
26-
console.log(example4);
27-
console.log(example5);
25+
const results = testCases.map(({ input }) => isBalanced(createTreeFromArray(input)));
26+
console.log(results);

‎example/6.Tree/0112.js

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -13,12 +13,13 @@
1313
*/
1414
var hasPathSum = function(root, targetSum) {
1515

16-
};
16+
};
1717

18-
const example1 = hasPathSum(); // root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 // true
19-
const example2 = hasPathSum(); // root = [1,2,3], targetSum = 5 // false
20-
const example3 = hasPathSum(); // root = [], targetSum = 0 // false
18+
const testCases = [
19+
{ input: [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum: 22, expected: true },
20+
{ input: [1,2,3], targetSum: 5, expected: false },
21+
{ input: [] , targetSum: 0, expected: false },
22+
];
2123

22-
console.log(example1);
23-
console.log(example2);
24-
console.log(example3);
24+
const results = testCases.map(({ input, targetSum }) => hasPathSum(createTreeFromArray(input), targetSum));
25+
console.log(results);

0 commit comments

Comments
 (0)