33. Binary Trees-3 (hard ques)

Hard problems-

  • LCA✅                                                             --- backtracking
  • nodes at a dist K✅⭐                                     --- modified BFS
  • min time to burn BT from a node✅                --- modified BFS    
  • construct BT from (pre & in) order✅             --- construct   
  • serialize & de-serialize BT✅                          --- BFS + string
  • flatten BT to LL✅⭐
    ---------------------------------------------------------
  • count total nodes✅                                        --- recursion
  • children sum property✅                                --- backtracking
  • Path from root to a given node✅                  --- backtracking
  • construct BT from (post & in) order✅          --- construct
  • max width (BT)✅                                          --- BFS + indexing
    --------------------------------------------------------
  • Morris in order Traversal✅⭐
  • Morris pre order Traversal✅

----------------------------------------------------------------------------------------------------------------------------NOTE:-
1. In trees question , mostly we try to optimize our solution from having:
space-n    to     space-H
2. max nodes in a level = 2^(level)
-----------------------------------------------------------------------------------------------------------------------------

DFS + backtracking-
1. Check condition for curr node (which should be checked for each node)
2. Explore paths for middle nodes
3. backtrack after exploring
3. Base case for leaf nodes at start of fn

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

1. Path from root node to a given node

For a node its left and right subtrees return T or F stating if they found target node
-------------
  1. if, cur node !=x we push curr into array and move to the left
  2. if, left returns true, we stop. 
  3.      left returns false, we go to right
  4. if both return F, then we pop back the node from the array & move back to ancestor.
  5. when a node = x, return a T and move back to ancestor with this new array till you go to root


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

2. LCA of 2 given nodes

Brute-
- find paths to both nodes from root and store paths in 2 vectors
- now last common element in both paths is LCA of these 2 nodes

Optimal-
in a single dfs approach, 
for every node, check if left & right subtree contains the 2 given nodes.


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

3. Max width

QUES- find max possible width amongst all levels
width of a level = no. of nodes between first & last non null nodes of this level
(also count null nodes that could have been present in that level)
------------
Method-1: bfs lagake last level m phunchke count krlo 
-----------
Method-2: BFS indexing 

1. store elements in queue as (node, idx) with left child = 2i & right child = 2i+1 for i-th node (0-based)
2. (width of each level = lastidx - firstidx+1)
3. ans = max of all widths
-----------------
Method-3: Normalized BFS indexing
To avoid overflow-
before indexing children of curr node using curr node's idx (i), we update (i) in a level to: ( curr idx - min index in this level )



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

4. Children Sum Property

modify nodes s.t. for every node, ( node->val = sum of its direct children's values )
NOTE- you can only increment value of a node
----------------------
1. firstly-
    if (cur_node < sum of children ) => increment cur_node value
    else, propagate cur_node value to its children
2. recurse inside tree, so you temporarily update all nodes as per step-1
3. now start updating nodes from bottom to top to correct values as per their children sum
---------------------
upar se niche pass krte rho values as per cond
fir niche se update krte krte upar le aao

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

5. Nodes at dist K from target node

APPROACH-
1. We will do bfs starting from target node 
2. each level pe, we explore 3 neighbors(left child, right child & parent) of all nodes in that level
3. for visiting parent node for a node in a BT, we store (node, parent) in a map
-----------
ALGO-
Step-1 : do BFS and store parents corresponding to each node in a map
Step-2: find target node by DFS
Step-3: Now, by BFS we move radially away from target node, till (dist <= K)
        3.1)  for each level in the queue, just push all valid neighbors (of each node in this                         level), into the queue and mark them visited.
        3.2)  after a level is traversed, increase dist by 1
        3.3)  when dist=k, nodes in queue are my ans
--------------



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

6. Min time to burn BT from given node

1. map parents of each node (as we would need them for exploring top neighbor in BFS)
2. find target node, by any traversal technique
3. start BFS from target node & do radial traversal ( do full BFS unlike stopping condition tak as we did in nodes at dist K problem )
4. keep a counter which increases if in a level any burning happens (counter wouldn't increase if a set of nodes in the queue, couldn't burn any neighbors)
5. Also, keep a visited nodes map as well


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

7. Count total nodes
( in a Complete Tree)

Brute- do any traversal and keep a counter which increments on curr node
            time: O(n)  space: O(H) 
------------------------------------------------------------

Better- time-(H^2)  space-O(H) ⭐⭐

for a perfect tree:  total nodes = (2^H)-1,                                        (LH= RH for all nodes)
for a complete tree: total nodes = 1 + [(2^LH) -1] + [(2^RH) -1]   (LH!=RH for all nodes)

1. for a node find Lh & Rh
2. if, Lh=Rh, find height of this subtree using at this stage only
     if, Lh!=Rh, then go to its children and repeat step 1 for both until u find a node 
     where Lh=Rh

We are doing this, bcoz we are trying to find heights using formula which only works for perfect BT (where Lh=Rh)

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

8. Constructing unique BT

Condition- all node values in the BT are unique
HINT- (pre: rLR) & (post: LRr), do follow up for any node in the respective arrays as well
------------------------------------------------------------------------------------------------------------

8.1) Constructing from pre & in-order:

1. select an element from preorder array as root
2. find this root's posn in the in-order array (may use a map)
3. in the in-order array, the elements(let x no. of such elements be there)to the left of root are in left subtree of root & those to the right are in right subtree

4. For the left subtree of root, the new (pre-order) array is the first x elements after root in original pre order array, similarly we get new arrays for right subtree as well.
5. now recurse on these new (in & pre) arrays for left & right subtrees
6. when a node gets a subtree returned, attach that subtree as a child to that node.
------------






















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

8.2) Constructing from post & in-order:

build right subtree first as post order is LRr, so after root there is right, if we see from back

-----------------------------------------------------------------------------------------------------------------------
#   Commonly used String functions-

1. s.append("v");
2. s.append('a' + ',');
3. int idx = s.find('a');
4. string y = x.substr(idx, no. of chars);
5. int x = stoi(s1);
6. string s2 = to_string(x);
------------------------
7. to read csv data: 

    string data = "1, 2, 3, 4, 5";
   
    stringstream ss(data);
    string temp;
   
    getline(ss, temp, ',');

---> temp reads chars from ss until first , appears & stores the char in temp & updates ss to point to idx after first comma
---------------------------
8. getline(cin, str);
---> reads str from input till enter is pressed
--------------------------------------------------------------------------------------------------------------------------

9. Serialize & de serialize a BT

serialize- encode BT into string
deserialize- decode string into BT

-----------------------------
Brute- (tree has unique node values)
we can have an encoded string which stores pre + in order traversal and we can re construct the tree using this string..
----------------------------
Better- (nodes can have duplicate values) 

1.) Serialize BT by BFS :-
--> store node's values as string & null values as # ; each separated by commas)

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

2.) Deserialize BT :-⭐

a) string se root node banao aur queue mein push kro
b) queue pe bfs lagao
c) bfs mein getline se left child lo curr node ka aur assign kro as a child & push into queue
d) bfs mein getline se right child lo curr node ka aur assign kro as a child & push in queue


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

10.1) Morris in-order Traversal

Here we will do traversal of tree without using any stack or recursion (i.e., in O(1) space)

LrR:- we will use threaded BT concept to come back to root after printing root--->left,
since once we come back to curr we can then just print curr and then print root-->right and done

1) if curr-->left exists & no thread to curr exists (i.e., temp-->right == NULL):
    1.1) temp use krke curr ke left subtree ke rightmost element pe point krao
    1.2) curr ko curr-->left mein bhejo
    1.3) repeat

2. if curr-->left == NULL:-
    2.1) print curr
    2.2) move curr to next node via thread

3. if thread exists for this curr (i.e., temp-->right != NULL):-
    3.1) remove the thread
    3.2) print curr
    3.3) move curr to curr-->right

--------------------------------------------------------------------------------------------------------------------------
10.2 ) Morris Pre order traversal

pre: rLR
so we will print a node, before adding a thread, unlike we did in morris in order

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

11. Flatten BT to LL

Ques- convert a BT's pre order traversal into a Linked List 
Condition- 
1. do in place
2. linked list uses treenode data type with left child always null for each node
----------------------------------------

Brute:     O(n) space

1. pre order traversal ke nodes ko vector mein store krlo
2. fir vector mein traverse krke curr node ka left child aur right child set krdo
3. last node ka right child bhi null hoga

---------------------------------------------------------
Better:- O(h) space
( Recursive Reverse Pre order traversal (RLr) )⭐

1. curr node ke right mein recurse kro, then left mein recurse kro
2. right child set kro using prev, then left child set kro
3. prev update kro
4. repeat

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

Extra-:  O(h)         [NOT FOR INTERVIEW]
( iterative Reverse pre order traversal (stack based soln) )-

1. curr node ke right child ko stack mein daalo
2. curr node ke left child ko stack mein daalo
3. curr node ka right child set kro & then left child set kro

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

Optimal:  O(1) space
(Morris traversal)
1. point prev (rightmost element of left subtree) to curr-->right
2. now make curr---->right = curr--->left
3. move to curr-->right


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

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