8000 added problems for binary search tree · yashkathe/DSA-with-Javascript@47cadbb · GitHub
[go: up one dir, main page]
Skip to content

Commit 47cadbb

Browse files
yashkatheyashkathe
committed
added problems for binary search tree
1 parent 3665ade commit 47cadbb

File tree

5 files changed

+210
-0
lines changed

5 files changed

+210
-0
lines changed

‎B2 LEETCODE-Medium/Trees/BST-to-greater-sum-tree.js

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/*
2+
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
3+
4+
As a reminder, a binary search tree is a tree that satisfies these constraints:
5+
6+
The left subtree of a node contains only nodes with keys less than the node's key.
7+
The right subtree of a node contains only nodes with keys greater than the node's key.
8+
Both the left and right subtrees must also be binary search trees.
9+
*/
10+
11+
var bstToGst = function (root) {
12+
let myMap = new Map();
13+
let sum = 0;
14+
15+
let dfs = (node) => {
16+
if (!node) return;
17+
18+
dfs(node.left);
19+
sum += node.val;
20+
myMap.set(node.val, sum);
21+
dfs(node.right);
22+
};
23+
24+
dfs(root);
25+
26+
console.log(myMap);
27+
28+
let dfs2 = (node) => {
29+
if (!node) return;
30+
31+
node.val = myMap.get(node.val);
32+
33+
dfs2(node.right);
34+
dfs2(node.left);
35+
};
36+
37+
dfs2(root);
38+
return root;
39+
};

‎B2 LEETCODE-Medium/Trees/Deepest-leaves-sum.js

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2+
/*
3+
Given the root of a binary tree, return the sum of values of its deepest leaves.
4+
5+
6+
7+
Example 1:
8+
9+
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
10+
Output: 15
11+
12+
Example 2:
13+
14+
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
15+
Output: 19
16+
17+
18+
*/
19+
20+
var deepestLeavesSum = function(root) {
21+
22+
let maxLvl = -1
23+
let sum = 0
24+
25+
const dfs = (node , lvl) => {
26+
27+
if(lvl > maxLvl){
28+
maxLvl = lvl
29+
sum = 0
30+
}
31+
32+
if(lvl === maxLvl){
33+
sum += node.val
34+
}
35+
36+
if(node.left) dfs(node.left, lvl + 1)
37+
if(node.right) dfs(node.right, lvl + 1)
38+
39+
}
40+
41+
dfs(root, 0)
42+
43+
return sum
44+
45+
};
46+
47+
// keep checking for max
48+
// if you find a new max change the maxVal and reset the sum
49+
// if its a maxVal then add to sum

‎B2 LEETCODE-Medium/Trees/Max-Binary-Tree.js

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/*
2+
You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
3+
4+
Create a root node whose value is the maximum value in nums.
5+
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
6+
Recursively build the right subtree on the subarray suffix to the right of the maximum value.
7+
8+
Return the maximum binary tree built from nums.
9+
10+
11+
12+
Example 1:
13+
14+
Input: nums = [3,2,1,6,0,5]
15+
Output: [6,3,5,null,2,0,null,null,1]
16+
Explanation: The recursive calls are as follow:
17+
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
18+
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
19+
- Empty array, so no child.
20+
- The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
21+
- Empty array, so no child.
22+
- Only one element, so child is a node with value 1.
23+
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
24+
- Only one element, so child is a node with value 0.
25+
- Empty array, so no child.
26+
27+
Example 2:
28+
29+
Input: nums = [3,2,1]
30+
Output: [3,null,2,null,1]
31+
*/
32+
33+
var constructMaximumBinaryTree = function(nums) {
34+
35+
if(nums.length === 0) return null
36+
37+
let max = Math.max(...nums)
38+
let index = nums.indexOf(max)
39+
let head = new TreeNode(max)
40+
41+
head.left = constructMaximumBinaryTree(nums.slice(0 , index))
42+
head.right = constructMaximumBinaryTree(nums.slice(index + 1))
43+
44+
return head
45+
46+
};

‎B2 LEETCODE-Medium/Trees/Sum-of-node-with-even-valued-grandparents.js

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
/*
2+
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
3+
4+
A grandparent of a node is the parent of its parent if it exists.
5+
6+
7+
8+
Example 1:
9+
10+
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
11+
Output: 18
12+
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
13+
14+
Example 2:
15+
16+
Input: root = [1]
17+
Output: 0
18+
19+
*/
20+
21+
// BFS Approach
22+
23+
var sumEvenGrandparent = function (root) {
24+
25+
if(!root.val) return
26+
27+
let sum = 0
28+
29+
let queue = [root]
30+
31+
while(queue.length > 0){
32+
let node = queue.shift()
33+
34+
if(node.val % 2 === 0){
35+
if(node.left && node.left.left) sum += node.left.left.val
36+
if(node.left && node.left.right) sum += node.left.right.val
37+
if(node.right && node.right.left) sum += node.right.left.val
38+
if(node.right && node.right.right) sum += node.right.right.val
39+
}
40+
41+
if(node.left) queue.push(node.left)
42+
if(node.right) queue.push(node.right)
43+
}
44+
45+
return sum
46+
47+
};
48+
49+
// DFS Approach
50+
51+
var sumEvenGrandparent = function (root) {
52+
53+
54+
let sum = 0
55+
56+
const dfs = (node , parent, grandParent) => {
57+
if(!root) return
58+
59+
if(grandParent && grandParent.val % 2 === 0){
60+
sum += node.val
61+
}
62+
63+
if(node.left) dfs(node.left, node, parent)
64+
if(node.right) dfs(node.right, node, parent)
65+
}
66+
67+
dfs(root, null, null)
68+
return sum
69+
70+
};

‎README.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -140,3 +140,9 @@ _-With JavaScript and TypeScript_
140140

141141
- [String](./B2%20LEETCODE-Medium/String/)
142142
- [Maxium Nesting Depth of two parethesis](./B2%20LEETCODE-Medium/String/Maximum-Nesting-Depth-of-Two-Valid-Parentheses.js)
143+
144+
- [Tress](./B2%20LEETCODE-Medium/Trees/)
145+
- [Binary Search Tree to Greater Sum tree](./B2%20LEETCODE-Medium/Trees/BST-to-greater-sum-tree.js)
146+
- [Sum of Deepest Leaves](./B2%20LEETCODE-Medium/Trees/Deepest-leaves-sum.js)
147+
- [Maximum Binary Tree](./B2%20LEETCODE-Medium/Trees/Max-Binary-Tree.js)
148+
- [Sum of Nodes with even valued grandparents](./B2%20LEETCODE-Medium/Trees/Sum-of-node-with-even-valued-grandparents.js)

0 commit comments

Comments
 (0)
0