32. Binary Trees-2 (bfs/dfs med problems)

Medium problems-

more imp----------------------

height ✅
diameter ✅
max path sum✅⭐

Height Balanced BT check✅
identical BT check✅
Symmetric BT check✅⭐

medium imp-------------------

Zig Zag traversal✅
Boundary Traversal✅
Vertical order Traversal✅⭐

less imp----------------------------

Top view ✅⭐
Bottom view✅
Right/ Left view✅

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

1. Max Depth of BT-

height(tree) = n(nodes) in longest path from top to bottom

time-N space-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 to give -1 for unbalanced case

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

3. Identical BT check-

in any traversal, compare elements of both trees together, at each step.
e.g., below is recursive pre order DFS traversal

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

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- O(n^2)
length of path passing through a node is (lh+rh) = (height of left subtree + height of right subtree)
use recursion to find lh & rh of each node & update maxi

(for nodes wali definition of diameter- take lh+rh+1 instead of lh+rh)

Optimal- O(N)

in the (nodes based) height code,
modify it to update an ans variable to store (edge based) length of path through a node

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

5. Max Path Sum-

( Path sum = sum of all node's in the path )

striver-

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

me-

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

My Trick to solve trees ques of recursion-

1. identify what variables to make
( e.g., for path sum corr to each node, we need left & right path sum of a node along with cur->val, so we use 2 variables: L & R, inside each recursive call )

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

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

6. Zig Zag BFS-

in 1st level traverse from L to R

in 2nd level, traverse from R to L

and so on....alternatively

Simple- do BFS & for each level store the elements of temp vector in a 2d vector &

for alternate levels, just reverse them before storing...

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

7. Boundary Traversal-(acw)

it is a 3-step process-

add left boundary nodes from top to bottom-->
add all leaf nodes-->
add right boundary nodes from bottom to top

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

1. store current node

2. if left exists ==> move to it

else ==> move to right

4. Repeat till u do not encounter a leaf node
------------------

5. Now, start a traversal & insert only the leaf nodes
-----------------

6. Now, for right boundary nodes, do similar stuff as u did for left boundary nodes its just opposite & here store in vector v2
------------------

8. Now store v1 elements as it is in ans but (store v2 elements in the answer in reverse order)

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

8. Vertical order Traversal⭐(BFS mapping)

time- nlogn space- n

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

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

----------
we will use: map<int,map<int,multiset>>mpp

where a key of outer map is vertical no.

& corresponding inner map to this vertical, stores (key, val) as (level no, nodes at that level)

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

so verticals are stored in sorted order

also, each vertical has (nodes as per) sorted levels (within that vertical)

multiset stores nodes at a posn (vertical, level) in sorted order, keeping in mind nodes may be duplicates at that posn also

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

use any traversal technique to fill map
e.g., for BFS- below we store nodes in queue as { node, posn } with posn = (col, row)

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

------------------------------------------------------------------------------------------------------------- 9.Top view- (BFS)

modify bfs mapping to store only first level nodes of each vertical instead of all nodes in a vertical

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

10. Bottom view- (BFS)

in bfs mapping, har vertical line mein last level wale nodes lelo

NOTE- for a posn with multiple nodes, choose rightmost side wala node

simple- in vertical traversal, update node of a key every time you find a node for that key, so that at last, we get the last node in that col at that key in the map.