31. Binary Trees-1 (traversals)

# Note-

1. Tree- a hierarchical data structure
2. Binary tree- each node has max 2 children
3. Types of nodes: root node / child node / leaf node
4. Sub tree= ( current node + all nodes beneath it )
5. Ancestors= all parent nodes above current node in its branch
--------------------------------------------------------------------------------------------------------------

# Types of trees-

1. Balanced BT:-     height of left & right sub tree differ by at most 1      ( height ~ log₂ n )

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

2. Degenerate tree- all nodes have 1 child only

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

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

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

# Implementation of a BT:-

Structure: a node pointing to a left node & a right node

Implementation: a struct with 2 pointers (left & right) and a value 

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

# Traversals-

1. BFS- using queue
---------------------------
2. DFS- using stack

1. recursive DFS                                     time: O(n)    space: O(H)
-----
2. iterative DFS

- (pre, in) using 1 stack🔥                      time: O(n)    space: O(n)   (H, for in-order) 

- (post) using 2 stacks⭐                        time: O(n)    space: O(n)
- (all in 1) using 1 stack                           time: O(n)    space: O(n)
------

# H can be worst N & best logN
--------------------------------------------------------------------------------------------------------------
Note-
Which traversal to prefer when ?

1. In Order: preferred where we want sorted order. e.g., BST
2. Post Order: mostly preferred (we want result bubbled upwards, result depends on children first)
3. Pre Order: Serialisation & building tree

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

4. we mostly work with recursive dfs, unless asked explicitly to work with iterative

5. Tree DP pattern:

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

# Recursive DFS

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

# BFS-

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

Using a queue

1. pop out and store all elements of current level from the queue to a temp vector
2. before adding a current level node to temp, we push its children into the queue for the next iteration
3. store elements of this level from temp to answer vector

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

# Iterative DFS-

1. 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

---------------------------------------------
2. 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 

-------------------------------------------------------------
3. Post Order (using 2 stacks):

st2.push (st1.top() )

st1.push(left)

st1.push(right)

repeat

stack 2 mein se top pop krte krte print karate rho

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

# Note-

1. Post Order 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

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

2. Post Order (using stack + vector)

Two stack wale mein-
instead of using 2nd stack, push it in a vector
& then reverse the vector.

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

# 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

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