Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 1cd6613

Browse files
Merge pull request knaxus#49 from knaxus/problems
Added BST
2 parents 05aa185 + 3475013 commit 1cd6613

File tree

4 files changed

+123
-4
lines changed

4 files changed

+123
-4
lines changed

‎README.md‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -24,18 +24,21 @@ Collection of interview questions with Unit Tests. Problems includes Data Struct
2424

2525
- [Implement Queue Using Stack](src/_DataStructures_/Stack/immitate-queue-using-stack)
2626
- [Baseball Game](src/_DataStructures_/Stack/baseball-game)
27-
- [Minimum Stack](src/_DataStructures_/Stack/min-stack)
27+
- [Find minimum in the Stack](src/_DataStructures_/Stack/min-stack)
2828
- [Balanced Parenthesis](src/_DataStructures_/Stack/balanced-parenthesis)
2929
- [Postfix Expression Evaluation](src/_DataStructures_/Stack/postfix-expression-evaluation)
3030
- [Remove Consecutive Repeated Digits](src/_DataStructures_/Stack/remove-consecutive-repeated-digits)
3131
- [Implement 2 Stacks using Single Array](src/_DataStructures_/Stack/2-stacks-using1-array)
32-
3332

3433
- [Queue](src/_DataStructures_/Queue)
34+
3535
- [Weave](src/_DataStructures_/Queue/weave)
3636

3737
- [Doubly Linked List](src/_DataStructures_/DoublyLinkedList)
38-
- [Suffix Tree](src/_DataStructures_/SuffixTree)
38+
39+
- [Trees](src/_DataStructures_/Trees)
40+
- [Binary Search Tree](src/_DataStructures_/Trees/BST)
41+
- [Suffix Tree](src/_DataStructures_/SuffixTree)
3942

4043
### Logical Problems
4144

@@ -67,7 +70,6 @@ Collection of interview questions with Unit Tests. Problems includes Data Struct
6770

6871
- [LRU Cache](src/_Algorithms_/lru-cache)
6972

70-
7173
### Path Finder
7274

7375
- [A\*](src/PathFinder/AStart)
Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
module.exports = class Node {
2+
constructor(value) {
3+
this.value = value;
4+
this.leftChild = null; // will be a node
5+
this.rightChild = null; // will be a node
6+
}
7+
};
Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
const Node = require('./Node');
2+
3+
class BinarySearchTree {
4+
constructor(value) {
5+
this.root = new Node(value);
6+
}
7+
8+
insert(root, value) {
9+
if (root === null) {
10+
const newNode = new Node(value);
11+
// eslint-disable-next-line no-param-reassign
12+
root = newNode;
13+
return root;
14+
}
15+
16+
if (value < root.value) {
17+
// eslint-disable-next-line no-param-reassign
18+
root.leftChild = this.insert(root.leftChild, value);
19+
return root;
20+
}
21+
if (value > root.value) {
22+
// eslint-disable-next-line no-param-reassign
23+
root.rightChild = this.insert(root.rightChild, value);
24+
return root;
25+
}
26+
return root;
27+
}
28+
29+
preorder(root) {
30+
/** returning an array so as to make testing easy */
31+
let arr = [];
32+
if (root === null) return [];
33+
arr.push(root.value);
34+
35+
const left = this.preorder(root.leftChild);
36+
arr = [...arr, ...left];
37+
38+
const right = this.preorder(root.rightChild);
39+
arr = [...arr, ...right];
40+
return arr;
41+
}
42+
43+
inorder(root) {
44+
/** left - root - right */
45+
if (root === null) return [];
46+
let arr = [];
47+
const left = this.inorder(root.leftChild);
48+
arr = [...left, ...arr];
49+
50+
// print root
51+
arr = [...arr, root.value];
52+
53+
const right = this.inorder(root.rightChild);
54+
arr = [...arr, ...right];
55+
return arr;
56+
}
57+
58+
postorder(root) {
59+
/** left - right - root */
60+
61+
if (root === null) return [];
62+
let arr = [];
63+
64+
const left = this.postorder(root.leftChild);
65+
arr = [...left, ...arr];
66+
67+
const right = this.postorder(root.rightChild);
68+
arr = [...arr, ...right];
69+
70+
return [...arr, root.value];
71+
}
72+
73+
search(root, value) {
74+
if (root === null) return false;
75+
if (value === root.value) return true;
76+
77+
if (value < root.value) {
78+
return this.search(root.leftChild, value);
79+
}
80+
if (value > root.value) {
81+
return this.search(root.rightChild, value);
82+
}
83+
return false;
84+
}
85+
}
86+
87+
// const bst = new BinarySearchTree(6);
88+
// console.log(bst.root);
89+
// bst.insert(bst.root, 4);
90+
// bst.insert(bst.root, 9);
91+
// bst.insert(bst.root, 2);
92+
// bst.insert(bst.root, 5);
93+
// bst.insert(bst.root, 8);
94+
// bst.insert(bst.root, 12);
95+
96+
// console.log(bst.root);
97+
98+
// const preorder = bst.preorder(bst.root);
99+
// console.log('Preorder Traversal - ', preorder);
100+
101+
// const inorder = bst.inorder(bst.root);
102+
// console.log('Inorder Traversal - ', inorder);
103+
104+
// const postorder = bst.postorder(bst.root);
105+
// console.log('Postorder Traversal - ', postorder);
106+
107+
// const search = 18;
108+
// console.log(`Search for ${search}`, bst.search(bst.root, search));
109+
110+
module.exports = BinarySearchTree;
File renamed without changes.

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /