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

Commit d6cd835

Browse files
yashkatheyashkathe
committed
added tree and binary tree problems
1 parent 561c904 commit d6cd835
< 8000 div class="prc-PageLayout-HorizontalDivider-CYLp5 prc-PageLayout-HeaderHorizontalDivider-bofyb" data-variant="line" style="--spacing-divider:var(--spacing-none);--spacing:var(--spacing-none)">

File tree

5 files changed

+175
-1
lines changed

5 files changed

+175
-1
lines changed

‎B1 LEETCODE-Easy/Binary Trees/leaf-similar-trees.js

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/*
2+
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
3+
4+
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
5+
6+
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
7+
8+
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
9+
10+
11+
12+
Example 1:
13+
14+
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
15+
Output: true
16+
17+
Example 2:
18+
19+
Input: root1 = [1,2,3], root2 = [1,3,2]
20+
Output: false
21+
22+
*/
23+
24+
const getLeafs = (root, arr) => {
25+
if(!root) return;
26+
27+
if(root.left === null && root.right === null) return arr.push(root.val);
28+
29+
getLeafs(root.left, arr);
30+
getLeafs(root.right, arr);
31+
32+
};
33+
34+
var leafSimilar = function(root1, root2) {
35+
let arr1 = [];
36+
let arr2 = [];
37+
38+
getLeafs(root1, arr1);
39+
getLeafs(root2, arr2);
40+
41+
if(arr1.length !== arr2.length) return false;
42+
43+
for(let i = 0; i < arr1.length; i++) {
44+
if(arr1[ i ] !== arr2[ i ]) return false;
45+
}
46+
47+
return true;
48+
49+
};
50+
51+
// Just find leaves of both trees and comapre them

‎B1 LEETCODE-Easy/Binary Trees/same-trees.js

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
3+
4+
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
5+
6+
7+
8+
Example 1:
9+
10+
Input: p = [1,2,3], q = [1,2,3]
11+
Output: true
12+
13+
Example 2:
14+
15+
Input: p = [1,2], q = [1,null,2]
16+
Output: false
17+
18+
Example 3:
19+
20+
Input: p = [1,2,1], q = [1,1,2]
21+
Output: false
22+
23+
*/
24+
25+
var isSameTree = function(p, q) {
26+
27+
if (!p && !q ) return true
28+
if (!p || !q ) return false
29+
30+
if(p.val !== q.val) return false
31+
32+
let leftVal = isSameTree(p.left,q.left)
33+
let rightVal = isSameTree(p.right,q.right)
34+
35+
return leftVal && rightVal
36+
};
37+
38+
/*
39+
keep checking that if values are not same return false and return with && operator because we want left right values to be true
40+
*/

‎B1 LEETCODE-Easy/Trees/post-order-traversal.js

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
Given the root of an n-ary tree, return the postorder traversal of its nodes' values.
3+
4+
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
5+
6+
7+
8+
Example 1:
9+
10+
11+
Input: root = [1,null,3,2,4,null,5,6]
12+
Output: [5,6,3,2,4,1]
13+
Example 2:
14+
15+
16+
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
17+
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
18+
*/
19+
20+
var postorder = function(root) {
21+
let arr = [];
22+
23+
const traverse = (root) => {
24+
if(!root) return;
25+
26+
for(let i = 0; i < root.children.length; i++) {
27+
traverse(root.children[ i ]);
28+
}
29+
arr.push(root.val);
30+
};
31+
32+
traverse(root);
33+
return arr;
34+
};

‎B1 LEETCODE-Easy/Trees/pre-order-traversal.js

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
Given the root of an n-ary tree, return the preorder traversal of its nodes' values.
3+
4+
Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)
5+
6+
7+
8+
Example 1:
9+
10+
11+
12+
Input: root = [1,null,3,2,4,null,5,6]
13+
Output: [1,3,5,6,2,4]
14+
Example 2:
15+
16+
17+
18+
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
19+
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]
20+
*/
21+
22+
var preorder = function(root) {
23+
24+
let arr = [];
25+
26+
const traverse = (root) => {
27+
if(!root) return;
28+
29+
arr.push(root.val);
30+
for(let i = 0; i < root.children.length; i++) {
31+
traverse(root.children[ i ]);
32+
}
33+
34+
};
35+
36+
traverse(root);
37+
return arr;
38+
};

‎README.md

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,15 @@ _-With JavaScript and TypeScript_
5454
- [Difference of sum](./B1%20LEETCODE-Easy/Arrays/difference-of-sum.js)
5555
- [Binary Search](./B1%20LEETCODE-Easy/Binary%20Search/)
5656
- [Count negative numbers in a sorted matrix](./B1%20LEETCODE-Easy/Binary%20Search/count-negatives.js)
57+
- [Binary Tree](./B1%20LEETCODE-Easy/Binary%20Trees/)
58+
- [Solve the boolean binary tree](./B1%20LEETCODE-Easy/Binary%20Trees/boolean-binary-tree.js)
59+
- [Find corresponding node in clone](./B1%20LEETCODE-Easy/Binary%20Trees/)
60+
- [Check if certain value exists in binary tree](./B1%20LEETCODE-Easy/Binary%20Trees/)
61+
- [Invert Tree](./B1%20LEETCODE-Easy/Binary%20Trees/)
62+
- [Find Max Depth of binary tree](./B1%20LEETCODE-Easy/Binary%20Trees/)
63+
- [Merge two trees](./B1%20LEETCODE-Easy/Binary%20Trees/)
64+
- [Check if tress have similar leaves](./B1%20LEETCODE-Easy/Binary%20Trees/leaf-similar-trees.js)
65+
- [Check if two trees are similar](./B1%20LEETCODE-Easy/Binary%20Trees/same-trees.js)
5766
- [Binary Search Tree](./B1%20LEETCODE-Easy/Binary-Search-Tree/)
5867
- [Increasing order search tree](./B1%20LEETCODE-Easy/Binary-Search-Tree/increasing-order-search-tree.js)
5968
- [Minimum Distance between bst nodes](./B1%20LEETCODE-Easy/Binary-Search-Tree/min-dist-between-nodes.js)
@@ -94,7 +103,9 @@ _-With JavaScript and TypeScript_
94103
- [Maximum Number of Words Found in Sentence](./B1%20LEETCODE-Easy/String/max-words-in-sentence.ts)
95104
- [Jewels and Stones](./B1%20LEETCODE-Easy/String/jewels-and-stones.ts)
96105
- [Goal Parser Interpretation](./B1%20LEETCODE-Easy/String/goal-parser.ts)
97-
106+
- [Trees](./B1%20LEETCODE-Easy/Trees/)
107+
- [Post order traversal](./B1%20LEETCODE-Easy/Trees/post-order-traversal.js)
108+
- [Pre order traversal](./B1%20LEETCODE-Easy/Trees/pre-order-traversal.js)
98109

99110
- [Medium Level Problems](./B2%20LEETCODE-Medium/)
100111
- [Linked List](./B2%20LEETCODE-Medium/Linked%20List/merge-nodes-between-zero.js)

0 commit comments

Comments
 (0)
0