# WTF

[TOC]

## Localize

x = 1

def f():
    print x

def g():
    print x
    x = 2

f()  #prints 1
g()  #throws an error
# UnboundLocalError: local variable 'x' referenced before assignment

This is because when you make an assignment to a variable in a scope, that variable becomes local to that scope and shadows any similarly named variable in the outer scope. Since the last statement in foo assigns a new value to x, the compiler recognizes it as a local variable. Consequently when the earlier print(x) attempts to print the uninitialized local variable and an error results.

## 284. Peeking Iterator
Follow up: How would you extend your design to be generic and work with all types, not just integer?
(1) Give addional flag
(2) Using a more unique value

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        if not iterator:
            return
        self.has_stored_next = False
        self.stored_next = None
        self.iterator = iterator

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if self.has_stored_next:
            return self.stored_next
        self.has_stored_next = True
        self.stored_next = self.iterator.next()
        return self.stored_next

    def next(self):
        """
        :rtype: int
        """
        if self.has_stored_next:
            self.has_stored_next = False
            return self.stored_next
        return self.iterator.next()

    def hasNext(self):
        """
        :rtype: bool
        """
        return True if self.has_stored_next else self.iterator.hasNext()

## Inoder Tree Traversal
### Iteration

def inoder(root):
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        print(roo.val)
        root = root.right

### Recursion

def inoder(root):
	if not root: return
    inoder(root.left)
    print(roo.val)
    inoder(root.right)

## 230. Kth Smallest Element in a BST

### Iteration (Suggested for this problem)

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right
        return None

### Recursion

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def kthSmallestHelp(root, k):
            if not root:
                return None, 0
            val, count = kthSmallestHelp(root.left, k)
            if count == k:
                return val, count
            count += 1
            if count == k:
                return root.val, count
            val, right_count = kthSmallestHelp(root.right, k - count)
            return val, right_count + count
        val, _ = kthSmallestHelp(root, k)
        return val

## 426. Convert Binary Search Tree to Sorted Doubly Linked List

### Iteration (Suggested for this problem)

class Solution:
    def treeToDoublyList(self, root):
        if not root:
            return None
        stack = []
        prev = None
        head = None

        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if not head:
                head = root
            else:
                prev.right, root.left = root, prev
            prev = root
            root = root.right
            
        prev.right, head.left = head, prev
        return head

### Recursion

class Solution:
    def treeToDoublyList(self, root):
        if not root:
            return None
        head = root
        while head.left:
            head = head.left

        def treeToDoublyListHelp(root, prev):
            if not root:
                return None
            prev_of_subtree = treeToDoublyListHelp(root.left, prev)
            if prev_of_subtree:
                root.left = prev_of_subtree
                prev_of_subtree.right = root
            elif prev:
                root.left = prev
                prev.right = root
            prev = root
            prev_of_subtree = treeToDoublyListHelp(root.right, prev)
            return prev_of_subtree if prev_of_subtree else prev

        latest = treeToDoublyListHelp(root, None)
        head.left = latest
        latest.right = head
        return head