34. BST

  • searching✅
  • ceil, floor (x) ✅
  • Kth smallest/ largest element✅
  • Check if BST or not✅
  • construct BST from pre order✅🔥  
  • LCA✅
  • insert node✅
  • in order successor & predecessor✅
  • delete node✅⭐  
  • BST iterator✅⭐
  • Two Sum✅⭐                  
  • Recover BST with 2 swapped nodes✅🔥         
  • size of largest BST in a BT✅🔥
----------------------------------------------------------------------------------------------------------------------

BASICS-

1. entire left subtree should be a BST
2  entire right subtree should be a BST
3. Ideally, L< N < R
    if we want duplicate: L <= N < R
4. Generally, height of BST = logN(base 2),  so advantageous.
For ex- for searching it will take logN in BST vs O(n) in a BT
5. in order traversal of a BST gives sorted tree 
---------------------------------------------------------------------------------------------------------------

1. Search in BST-

--------------------------------------------------------------------------------------------------------------

2. Ceil & floor of key in BST

ceil(x)  : ( smallest value  >=x )










------------------

floor(x) : (largest value  <=x )









-----------------------------------------------------------------------------------------------------------
3. Insert & delete a node in a BST-

there can be multiple possibilities, below method is as per leaves

inserting-
---------------------------------------------------------------

Deleting-⭐
Case-1: target node has 0 children✅
Case-2: it has 1 child (either left or right child)✅
Case-3: it has 2 children (either find inorder predecessor or inorder successor of this node)
Case-4: it is root node✅
Case-5: tree is empty✅



---------------------------------------------------------------------------------------------------------------------------
4. Kth smallest-

BRUTE- (time-n, space-n)

vector mein inorder traversal store krke (k-1)th print krdo
--------------------------------------
OPTIMAL- (time- n, space-n)

 we will use a counter
if we use morris traversal, then we can optimize space to O(1) 






























----------------------------------------------------------------
NOTE-
kth largest = (n-k+1)th smallest, where n is total nodes
-------------------------------------------------------------------------------------------------------------------------
5. Validate BST-

We will use ranges


-----------------------------------------------------------------------------------------------------------------------------
5. LCA in BST-
Time- O(H)

LCA is 1st poi of paths of both nodes from root
1. both nodes on right => move right
2. both nodes on left => move left
3. one on right and one on left =>stop, as first diversion is ans



-----------------------------------------------------------------------------------------------------------------------------
6. Construct BST from pre-

Better: sort given pre order and we get in order, then same as construct BT from pre + in
time- O(nlogn)        space- O(n)



----------------------------------------------------------
Optimal: use concept of ranges as we did in validate BST question
               here we only need upper bound 
               upper bound for left child is curr node, 
               upper bound for right child is same bound as that of curr node
 time- O(n)        space-O(1)


-----------------------------------------------------------------------------------------------------------------------------
7. in-order predecessor & successor-

successor-  smallest element > curr node
predecessor- largest element < curr node

for successor-  if node < target =>  move right
                      - if node > target => update ans & move left 
                      - repeat, while root is not NULL

similarly do for predecessor
---------------------------------------------------------------------------------------------------------------------------
7. BST iterator-

QUES-
You’re given a BST, you need to build an iterator that:

next() → gives the next smallest element (in-order traversal order).
hasNext() → tells if there’s still a next element.

Basically: turn the BST into a sorted array, but without actually building the array (because that wastes memory).
----------------------------
Approach-
1. we will use a stack to store all left elements
2. whenever next is called, we pop out from stack and return it.
3. If popped out element has right child, we push right child and all its left descendants into stack
4. repeat
--------------------------------




----------------------------------------------------------------------------------------------------------------------------
8. Two sum-

Brute-  time-O(n)    space- O(n)

inorder se sorted array banake arrays wala 2 sum lgado

------------------------------------------------------------
Better-  use BST iterator (space- O(h))

Get asc and desc elements simultaneously using BST iterator
and use 2 sum



--------------------------------------------------------------------------------------------------------------------------
9. Recover BST-

given a BST where 2 nodes are swapped. recover original proper BST.
  
BRUTE- time: O(nlogn) , space: O(n)
1. store current BST's inorder traversal
2. store another vector mein sorted version of this inorder
3. dono ke har element ko match kro jo different aaye usko inorder ke mein replace mardo with sorted wale se

BETTER- time:O(n), space:O(n)
1. agar poore inorder mein 1 hi dip hai toh adjacent wale swap hue the, aur agar 2 dips hain toh non adjacent wale swap hue the
2. while doing in order using recursion, we will store these dip wale nodes
3.1) swapped elements are adjacent:- simple swap maardo dono ko
3.2) non adjacent: jo humne do nodes mein store kre the usme first dip mein bada wala, second dip mein chote wala store kra tha, in dono ko swap maardo

------------------------------------------------------------------------------------------------------------------------
10. Size of largest BST in a BT-
Brute-  O(n^2)
1. pass every node to validate BST fn
2. jispe true aayega vo waale node ko root maanke us subtree ke nodes count kro
--------------------------------------------------
Optimal-   time-O(n)         space-O(1)


1. For every node, find largest on left & smallest on right, with size of BSTs on each side
2. Now check if this node lies between these two & return total size = ( 1 + x + y )
3. if a node do not satisfies condition, then take max count out of 2 child subtrees of it

We will move from (bottom to top) using POST ORDER, since we want size & largest element of left, then size and smallest element of right, then we check condition on root 

Leaf node is a BST, and it is stored as {node, node, 1}
For null node-> we store {INT_MIN, INT_MAX, 0}

We will compute: {largest, smallest, size} for every node, from bottom to top of tree


---------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more