Movatterモバイル変換

[0]ホーム
URL:

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

Commit65c44f4

Browse files
committed
chekc if a binary search tree
1 parent17a8b6c commit65c44f4

File tree

4 files changed

+132
-25
lines changed

4 files changed

+132
-25
lines changed

‎Binary-Search/BST-Basics.js

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
/* How would you create a binary search tree?
2+
Answer: to create a tree I need a node. a node in a tree looks like below
3+
*/
4+
5+
functionNode(val){
6+
this.value=val;
7+
this.left=null;
8+
this.right=null;
9+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/* GENERAL THEORY - A Binary Search allows you to search a sorted array by repeatedly splitting the array in half.
2+
3+
A binary search works by checking if our search value is more than, less than, or equal to the middle value in our array:
4+
5+
If it’s less than, we can remove the right half of the array.
6+
If it’s more than, we can remove the left half of the array.
7+
If it’s equal to, we return the value
8+
The catch here is that the array must be sorted — i.e. the values must be in order for a binary search to work.
9+
10+
When working with large chunks of data, it is much faster to use a binary search because with each iteration you remove 1/2 of the array’s wrong values, instead of just one wrong value. */
11+
12+
// SOLUTION-1
13+
14+
binarySearch=(arr,value)=>{
15+
16+
letestimatedIndex,minIndex=0,maxIndex=arr.length-1;
17+
18+
while(minIndex<=maxIndex){
19+
20+
estimatedIndex=Math.floor((minIndex+maxIndex)/2);
21+
22+
if(arr[estimatedIndex]===value){
23+
returnestimatedIndex
24+
}
25+
elseif(arr[estimatedIndex]<value){
26+
// then start the next search from middle position towards right
27+
minIndex=estimatedIndex+1;
28+
}
29+
else{
30+
// i.e. the value is in the left half, so reduce the maxIndex to 1 less than the middle position
31+
maxIndex=estimatedIndex-1
32+
}
33+
}
34+
}
35+
36+
console.log(binarySearch([2,4,1,5],5));
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
/* https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
2+
3+
A program to check if a binary tree is BST or not
4+
5+
A binary search tree (BST) is a node based binary tree data structure which has the following properties.
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+
From the above properties it naturally follows that:
11+
• Each node (item in the tree) has a distinct key.
12+
13+
So, in another word - Binary tree is a tree data structure in which each node has at most two child nodes.
14+
15+
A binary search tree (BST) is a rooted binary tree, whose internal nodes each store a key and each have two distinguished sub-trees, commonly denoted left and right.
16+
– The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.
17+
18+
*/
19+
20+
/* SOLUTION - Traverse the tree in-order. Compare the current element with the previous element
21+
Note: This approach can not detect duplicates. We will assume all nodes in the tree have unique values. */
22+
23+
functionBinaryTree(){
24+
this.root=null;
25+
}
26+
27+
// Variable to hold the data of the last node
28+
letlast_logged;
29+
30+
functionisBST(root){
31+
32+
// base case
33+
if(root===null){
34+
returntrue;
35+
}
36+
37+
// verify and recurse left
38+
if(!isBST(root.left)){
39+
returnfalse;
40+
}
41+
42+
// verify the current node.
43+
if(last_logged!==null&&root.data<=last_logged){
44+
returnfalse;
45+
}
46+
47+
// Console.log the current data for debugging and also update the last_logged value with the current node's value
48+
console.log('Current node : ',root.data);
49+
last_logged=root.data;
50+
51+
// verify and recurse right
52+
if(!isBST(root.right)){
53+
returnfalse
54+
}
55+
56+
// If none of the false is encountered above, then finally return true.
57+
returntrue;
58+
59+
}
60+
61+
// Test case- Create a Binary Tree as a sample input
62+
63+
varroot={
64+
data :8,
65+
left :null,
66+
right :null
67+
};
68+
varn1={
69+
data :10,
70+
left :null,
71+
right :null
72+
};
73+
74+
varn2={
75+
data :6,
76+
left :null,
77+
right :null
78+
};
79+
80+
letBT=newBinaryTree();
81+
BT.root=root;
82+
83+
// Create a binary search tree
84+
root.left=n2;
85+
root.right=n1;
86+
87+
console.log(isBST(BT.root));

‎Search/binary-search-basic.js

Lines changed: 0 additions & 25 deletions
This file was deleted.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp