<aside> 📚

Definitions:

• Balanced Binary Tree
• Self-Balancing Binary Search Trees
• Complete Binary Tree
• Binary Search Tree
• Tail Recursion </aside>

<aside> ✍️ 经典Code

• Recursion：理解recursion function的意义，坚信recursion会把你想要的反值。i.e Delete target node:
• Recursion helper function的output 可以跟最终output不一样。 helper function output是遍历于给上一层传值。怎么判断helper function return什么？ 问 3 Recursion Key Questions
• isBalanced：Replace a boolean output to an Integer in recursion function to store more info
• isTweakedIdentical：Break down a complex problem to simple problems. This one also has crazy amount of corner cases… ⇒ 写recursion function需要所有case都要包括在either base case或者recursion rule里。
• BST问题: 用BST特征来搜索 ⇒ 要么往左要么往右，直上直下的搜索
• BST的两种题型和模版：i.e. Closest Number in BST(模版1)， K Smallest Element in BST(模版2)
• BST经典Recursion & Iterative解法对比 i.e. Get Keys in Binary Search Tree in Given Range Keep in mind that the recursive approach might require more memory due to the function call stack for deep BSTs. The iterative approach is generally more memory-efficient.
• Parent Pointer：Solve it as Linked List problem instead of using Recursion
• PathSum Equals to K：DFS to find all possible path sums that are equals to k (root-to-leaf || any-to-any)
• Tree Traversal (Iterative) 的万能代码 - Using Two Stacks
• K-nary Tree 里 recursively explore solution in left and right subtree的方法
• Path Problem can have two differnt approaches - Top Down & Buttom Up </aside>

<aside> 🌵 Table of Contents

</aside>

Tree Traversal

<aside> ✍️ Binary Tree Traversal

• Objective: 没有重复，没有遗漏的把所有的node都遍历一遍。

• Order of Traversal：

  	遍历顺序	打印时的访问次数
  PreOrder Traversal	根左右	1st time visit
  InOrder Traversal	左根右	2nd time visit
  PostOrder Traversal	左右根	3rd time visit

Iterative Tree Traversal Logic：

Key Points：所有节点都需要没有遗漏的打印。每一轮的while loop代表当前处理的TreeNode cur。在每一层while loop遍历时，因为我们没有recursion call stack，不能直接压栈去处理当前层的node。那怎么去把当前碰到的root和 left and right subtree没有遗漏的处理？

• PreOrder Traversal，根左右: 先打印自己，确保左子树没得打印了之后，再打印右边。⇒ 所以在当前层碰到右子树时，先压在的最最下面，最后打印 ⇒ Therefore，we can use a Stack.
• InOrder Traversal, 左根右：先把左边的全部打印完，再打印自己，再打印右边。⇒ 所以在当前层碰到根时，先压在最下面，等所有的左子树打印完再打印。⇒ Therefore, we can use a Stack
• PostOrder Traversal, 左右根：先把左右所有的节点打印完，再打印根节点。可以用两个Stack - nodeStack & countStack。确定当前的visit是第三次的时候，把当前值打印出来。
• Level Order Traversal：从上到下，从左到右，按先后顺序一个一个遍历读取，FIFO。⇒ Therefore, we can use a Queue
• Zig Zag Order Traversal: 每层遍历顺序 alters。不能用FIFO或者LIFO的顺序去consistently pop，需要更dynamic的data structure ⇒ Therefore, we use a Deque. </aside>

<aside> 📌 易错点：

• Level Order Traversal: Store the current size of queue tempSize, this will be the size of the current level of the tree. </aside>

Date: June 23, 2023

Problem: PreOrder Traversal

Date: July 22, 2023

Problem: InOrder Traversal

Date: July 22, 2023

Problem: PostOrder Traversal

Date: July 22, 2023

Problem: Level Order Traversal