32. Binary Trees-2 (BFS/ DFS med problems)

Note-

1. Height of tree = no. of nodes in longest path = Max depth of a tree
2. Height of a node = 1 + max( LH, RH )
3. Path length of a path through a node = no. of edges in a path with this node as HCA
                                                                       = no. of edges in left tree + in right sub tree
                                                               = Height of left sub tree + height of right sub tree
4. Diameter of a tree = max path length
5. Path sum = sum of all nodes in the path
-----------------------------------------------------
# Pattern to solve tree based problems:-

1. identify what variables to make, inside each recursive call.
( e.g., for path sum => we need left & right path sum of a node => use L & R )

2. identify default values for these var & how to find values for these

3. identify how to update the ans (like if we want to add 2 variables for ans, etc.)

4. identify what should a child node return in a recursion call

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

1. Max Depth of BT-

time: O(n)    space: O(n)

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

2. Balanced BT check-

it means for every node:     [ H(left) - H(right) ] <=1

Brute-  time: O(n^2)

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

Better-  time: O(n)

modify the height code 

each node returns: 
height of sub tree, if balanced
and, -1 if unbalanced

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

3. Identical BT check-

use any traversal to compare elements
-----------
e.g., recursive pre order DFS:

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

4. Diameter(BT)-⭐

Diameter = no. of edges in longest path b/w any 2 nodes
This path may or may not pass through the root
------------------------------------------------------
Brute- time: O(n^2)   

- for current node, find path length (= height[left sub tree] + height[right sub tree] )
- update answer variable
- recurse on children to repeat, until you reach null

(for nodes wali definition of diameter, take 1+lh+rh instead of lh+rh, while updating maxi)

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

Optimal-  time: O(N)

modify height code (nodes based wala)

1. get left path length & right path length
2. update answer variable with total no. of edges in the current node's path
3. each child node will return max no. of edges associated to it in a path (i.e., max height)

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

5. Max Path Sum-⭐

1. Get max path sum of left and right sub tree
2. update answer variable with current node's path sum
3. each child node will return max path sum due to that node 

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

6. Symmetric BT check-⭐

Left sub tree = mirror image of right sub tree

1. check if current node both sub trees are same or not
2. if they are same, then just recurse on appropriate children of these nodes & check if they are same or not.
3. If both children return true, then trees are symmetric.
4. Base case means when either of the current node is null, then do a comparison b/w the 2 nodes 

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

7. Zig Zag BFS-

Ques- print like this:
1st level: L to R      ;      2nd level : R to L     ;     and so on....

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

Approach-

in BFS, for alternate levels, just reverse the elements in temp before storing in answer vector

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

8. Boundary Traversal-(ACW)

1-2-4-8-9-6-7-3

Approach- time: O(3n)   space: O(2n)

using multiple DFS traversals
----------------------------

1. Add left boundary nodes (from top to bottom)

- if current node is non leaf node, store in v1

- if, left exists => move to left

  else               => move to right

- Repeat (till u do not encounter a leaf node)
----------------------------
2. Add all leaf nodes

- do any dfs traversal to store all the leaf nodes of the tree
------------------------------
3. Add right boundary nodes (from bottom to top)

- similar to left boundary nodes code...
- repeat these steps till you find a leaf node:
    - store current node in v2
    - if right exists => move to right
      else => move to left 
-------------------------------

4. Now store v1 elements as it is in ans & v2 elements in reverse order in ans

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

9. Vertical order Traversal⭐
(BFS mapping)

Question-
for each vertical there are multiple unique levels

there can be more than 1 nodes at a level within a vertical, such nodes need to be sorted

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

Approach- time: O(NlogN)    space: O(n)

( we prefer BFS since we process nodes as per horizontal distance from root & also order inside a column matters & order needs level awareness )
-------------------------
1. we use BFS traversal to fill an ordered map

- map< int, map<int,multiset> >mpp : [col, (row, nodes)]  =  [ vertical, (level, node) ]

- in BFS, we store nodes in queue as { node, posn } with posn = (row, col) = (level, vertical)

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

So, verticals are stored in sorted order. Also, each vertical has (nodes as per) sorted levels (within that vertical)

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

2. store elements from map into an answer vector from left to right columns

--------------------------------------------------------------------------------------------------------------- 10. Top view- (BFS)

modified vertical traversal :  in each vertical, store only first level nodes.

map and queue now do not store row & only stores col, since we want to store only first node in every column

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

                                     11. Bottom view- (BFS)

modified vertical traversal
only take last level nodes in each vertical

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

now we update node of a vertical every time, so that at last, we get the last node in that col.

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

12. Right view-

1. Using BFS

modify BFS so it only takes the last element at each level

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

2. Using recursive DFS- (may ignore)

do a reverse pre order traversal

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