31. Binary Trees-1 (traversals)

Intro-

It is a hierarchical data structure.

Binary means a node has max 2 children

Types of nodes- root node, child node, leaf node

Sub tree- the current node and all nodes beneath it together form a subtree

Ancestors- all parent nodes above current node in its branch

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

Types of trees-

1. Balanced BT:-     left & right subtree's height differ by at most 1,      ( height ~ log₂ n )

  • Perfect BT:-     all internal nodes have 2 children & all leaf nodes are at same level.
  • Complete BT:- all levels except last are completely filled & last level has all nodes as left as possible

2. Degenerate tree- all nodes have 1 child only

  • Skewed Trees- special trees where all nodes lean on one side  (height ~ n)

3. Full BT:- every node has 0 or 2 children

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

Representation:-

a struct with 2 pointers (left & right) and a value 
in trees we need root node






















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

Traversals-

1.BFS✅                                                           time- O(n)  ;   space- O(n) 
-----------------------------------------------

1. recursive DFS✅                                          time- O(n)  ;   space- O(H)
2. iterative  DFS using 1 stack🔥                     time-O(n)   ;   space- O(n)   (H, for in-order) 
--------------------------------------------------
# iterative DFS (post order) using 2 stacks⭐ time-O(n)   ;   space- O(n)
# iterative DFS (all in 1) using 1 stack✅        time-O(n)   ;   space- O(n)

# H can be worst N and best logN
-----------------------------------------------------------------------------------

1. Recursive DFS










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

2. BFS-

  • current level wale saare elements queue mein se pop karke temp mein store krlo
  • saath mein har element k children ko queue mein push krte rho
  • temp mein jo ek level waale saare elements hai vo ans mein push krdo
  • ab next level walo k liye repeat krte rho...

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

3. iterative DFS (using stacks)-

a) Pre Order (using 1 stack)            
1. print st.top & pop out this element
2. push its right child and then left child into stack (opposite of expected since LIFO)
3. repeat

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

b) In Order (using 1 stack)   ðŸ”¥ðŸ”¥     

go deepest in left pushing all nodes into stack
when you get null then pop & print st.top 
now go to right of this last node and again repeat. 

1. till element != NULL , push kro AUR left mein jaao
2. when element ==NULL, print st.top and pop it and move to its right & repeat step 1 

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

c) Post Order ⭐

  • METHOD-1:  using 2 stack         

st2.push (st1.top() )
st1.push(left)
st1.push(right)
repeat

stack 2 mein se top pop krte krte print karate rho

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

  • METHOD-2: using 1 stack (rare)
1. push into stack
2. go as left as possible
3. when left is finished, then:
    if top ka right exists, then move ptr to right and repeat above steps
    else, pop & print and keep doing this(move to top)till u exit current branch
4. REPEAT

------------------------------------------------------------
  • Method-3 : Using 1 stack & 1 vector
2 stack wale mein hi instead of using 2nd stack, push it in a vector and then reverse the vector

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

4. Pre, In, Post (all 3) using 1 stack-

STEP-1:
we will store elements in a stack as (node, num)
pushing root node initially s.t. it's pairwise num will be 1 

STEP-2:
see st.top ka num & push this node into reqd vector & ++ corr num
1: pre
2: in
3: post (no ++ is reqd & pop this pair from stack now)

STEP-3:
for pre case:   if  left exists, push it into stack
for in   case:   ,,   right  ,,      ,,      ,,   ,,   ,, 

STEP-4:
Repeat from step 2 till stack becomes empty

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

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