114. Flatten Binary Tree to Linked List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None:
            return
        # I am at a leaf
        if root.left is None and root.right is None:
            return
        
        # I have a left child AND/OR a right child
        self.flatten(root.left)
        self.flatten(root.right)
        
        if not root.left:
            return
        
        temp = root.right
        root.right = root.left
        root.left = None
        # find the last element of root.right
        curr = root.right
        
        if curr is not None:
            while curr.right is not None:
                curr = curr.right

            curr.right = temp

Tree Notes 27-07-2020

4 Types of traversals.
3 DFS
	Pre-order (root--left--right)
	In-order (left--root--right)
	Post-order (left--right--root)
1 BFS
	In-order traversal
Binary Trees (BT) are a recursive data structure.
	A BT root's left node is also a BT.

DFS recursive
def preorder(root):
	if not root:
		return
	print(root)
	preorder(root.left)
	preorder(root.right)

The same is for other DFS recursive approaches.

Stack is LIFO because I want to fully 
Stack enables backtracking.
	Backtracking
		I explore a node
			Build solution with node's value
			Push children to stack

	(push children to stack),  and then is all about backtracking. Once I explore the top fully, it is popped and the next element is the 
We have to maintain the address to the 

Pre-order

Do the work on the root NOW
then explore the left.
Before doing so, push root on the stack so I can get back to here.

PUSH



Problems

700. Search in a BST
	DFS Approach
		Takeaway:
			TODO
		Code
			def dfsSearch(root, val):
				if not root:
					return root
				if root.val == val:
					return root
				return search(root.left, val) or search(root.right, val)
	iterative using stack
		Takeaway
			TODO
		Code
			def iterativeSearch(root, val):
			if root is None:
				return root
			q = []
			q.append(root)

			while q:
				node = q.pop()
				if node.val == val:
					return node
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			return None

938. Range Sum of BST
	Problem
		Given a BST, get sum of all values of nodes between 'L' and 'R'
	Takeaway
		Enough to consider root, and the rest are subproblems.
	Code
		def rangeSumBST(root, L, R):
			if root is None:
				return 0
			total = 0
			if L <= root.val <= R:
				total += root.val
			total += rangeSumBST(root.left, L, R)
			total += rangeSumBST(root.right, L, R)
			return total
617. Merge Two Binary Trees
	Problem
		Given 2 BSTs, merge them together.
		If nodes overlap, result node is the sum of the two.
		Else, if one exists, the non-None node is the node.

	Takeaway
		Force myself by thinking ONLY about solving for the root node.
		The rest of the tree will be solved by the recursion.
	Code
		def mergeTrees(t1, t2):
			if not t1 and not t2:
				return None
			if not t1 or not t2:
				return t1 or t2
			
			t1.val = t1.val + t2.val
			t1.left = self.mergeTrees(t1.left, t2.left)
			t1.right = self.mergeTrees(t1.right, t2.right)
			return t1
590. N-ary Tree Postorder traversal
	Problem
	Takeaway
	Code
		Recursive
			def recursive(node, res):
				if root is None:
					return res
				if root.children:
					for child in children:
						recursive(child, res)
				res.append(node.val)
				return res
			def postorder(root):
				return recursive(node, [])
590. N-ary Tree Postorder Traversal (get back)
	Problem
		Given an n-ary tree, return postorder traversal.
	Takeaway
		When you have to do a post order, data structure is a stack to traverse the tree.
		Output array needs to be reversed.
	Code
		def postorder(root):
			output = []
			stack = []

			if not root:
				return output
			
			stack.push(root)
			
			while stack:
				node = stack.pop()

				output.append(node.val)

				for c in node.children:
					stack.push(node)
		return output[::-1]
965. Univalued Binary Tree
	Problem
		Return true if every node is univalued.
		Defined as if every node has the same value.
	Takeaway
		Most problems compare across node and its children
		My comparison is on a parent/child.
		That is why the DFS is passed in root/child.

		In iterative approaches, it might make more sense to pass parent/child into the stack frame
		In recursive approaches, it makes more sense to find what my "node" is and where my "subproblems" are.
	Code
		def isUnivalTreeUtil(root, prev):
			if root.val != prev.val:
				return False
			
			l = isUnivalTreeUtil(root.left, root)
			r = isUnivalTreeUtil(root.right, root)
			return l and r

		def isUnivalTree(root):
			return isUnivalTreeUtil(root, root)

		def isUnivalTree(root):
			if not root: return True

			if root.left and root.val != root.left.val:
				return False
			if root.right and root.val != root.right.val:
				return False

			return True
589. N-ary Tree Traversal
	Problem
	Takeaway
	Code