BINARY-SEARCH-TREE-DSA

Binary-search-trees-in-JavaScript

No.	Questions
	Binary search tree
1	Binary-search-tree-and-its-applications
2	Height-balanced-BST
3	BST Insertion
4	Inorder successor and predecessor
5	BST Delection

| 1 | Binary-search-tree-and-its-applications

1.1 Binaary search Tree

Left sub -tree :LT, Right sub- Tree: RT, Where P: Parent

Let we assume that 'LEFT' :sub-tree ≤ P' is called left side smaller

Let we assume that 'RIGHT' :sub-tree ≥ P' is called right side is bigger

1.2 Binary search Tree

same like wise LEFT PARENT value
KEY REPRESENTS values of the tree and CURRENT tells the value of PARENT
When ever KEY values LESS then the CURRENT PARENT value then its represents the LEFT side of the tree

Select the LEFT side elements of the KEY values which are LESS than PARENT TREE

Same like wise RIGHT PARENT value
KET REPRESENTS values of the tree and CURRENT tells the value of PARENT
When ever KEY values GREATER then the CURRENT PARENT value then its represents the RIGHT side of the tree
select the RIGHT side elements of the KEY values which are GREATER than PARENT TREE

1.3 Binary serch tree key and node values

KEY === CURRENT is equal to parent value
DISTENCE From root node to fargest d done is 4
Distence feom fargest d node to root node is HEIGHT of the Tree
search is taken as o(h) time,I can search any type of tree
height of the Tree is also 4 and the number of compressions is also 4
IMP 11.19
Binary Search search TREE=> o(h) and in an unsorted array |---------------| o(n)
search time complexity is o(h) times
p
restrict the hight of the array in an unsorted array we need to ettrate o(n) times
let say construct a tree a binary search tree then h =log(n) the SEARCH will becomes =>o(h) means SEARCH => o(logN)

if h == logN NODES =7 AND HEIGHT H = log 7 2 => 3

IF h == logN NODES =4 and HEIGHT h = log 4 4 =>

in a stand binary standard there is non restrection

In a balanced binary search tree it is directly it is h= o(logn) and search = o(logn)

Search complexity improve dramatically o(n), if h == logn
Search=> o(logn)
Nodes , N =7 anf HEIGHT , h=log7 2
|h(l) - h(r)| ≤ 1

| 2 | Height-balanced-BST

HSTHeight-balanced-types

Red Black Tree

AVL trees

'WHITE", 'RED BLACK TREE " are important when compared among these 'AVL" is more important in Binary search tree

| 3 | BSTinsertion

BST insertion types

Let insert new element 13 and compare from root element and find correct position for 13

Attach the new node

First compare Root Node 10 is (greater then or equal) or (less then or equal) BST as a rule is that root element is greater then ket lements it is left side of the BST

Second if is some case ROOT element is less than KEY elements then it is belongs to RIGHT HAND side of the tree

INSERT '13' > 10 ------> it belongs to LEFT SIDE of the TREE

INSERT 13 < 15 ------> it belongs to RIGHT SIDE of the TREE

INSERT 13 > 12 ------> it belongs to LEFT SIDE of the TREE that means 12 RIGHT SIDE , LAST ELEMENT

INSERT 16' > 10 ------> it belongs to RIGHT SIDE of the TREE

INSERT 16 > 15 ------> it belongs to RIGHT SIDE of the TREE

INSERT 16 < 19 ------> it belongs to LEFT SIDE of the TREE that means 19 LEFT SIDE, LAST ELEMENT

TC => O(h)

HEIGHT OF THE TIME COMPLEXITY

| 4 | Inorder successor and predecessor