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

Inorder successor Inorder predecessor

Inorder successor

Inorder predecessor

Inordersuccessor 15(9) = 10 15(3) = 5 15(12) = 15

Inorder predecessor Ip(9) = 8 Ip(7) = 5 Ip(12) = 11

| 5 | BTS Delection

Inorder successor less then parent node it comes under left side

Greater then parent node and the key values are greater than parent node

these are dependes on nodes and key values

No child

No child

No child in in BST delection type

Single child

Single child

Two children