Note:
During practice, also practise how to think, how to take proper note to assist thinking, and how to draw the right helper diagram. For example, how to draw:

• queue
• stack

How to draw each iteration of while/for loop. How to draw recursion / divide-and-conquer's thinking process.

Questions with easy difficulty:

110. Check Balanced Binary Tree

• This problem is generally believed to have two solutions: the top down approach and the bottom up way.

1.The first method checks whether the tree is balanced strictly according to the definition of balanced binary tree: the difference between the heights of the two sub trees are not bigger than 1, and both the left sub tree and right sub tree are also balanced. With the helper function depth(), we could easily write the code;

class solution {
  public: 
  int depth (TreeNode *root) { 
    if (root == NULL) return 0; 
    return max (depth(root -> left), depth (root -> right)) + 1; 
  } 
  bool isBalanced (TreeNode *root) { 
    if (root == NULL) return true; 
    int left=depth(root->left); 
    int right=depth(root->right); 
    return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right); 
  }
};

# use bottom up approach: 
class Solution(object):
    def isBalanced(self, root):
        return self._isBalanced(root) != -1
        
    # think: can we do it without helper function? 
    # how should we modify the return result in that case? 
    def _isBalanced(self, root):
        if not root:
            return 0
        left_height = self._isBalanced(root.left)
        if left_height == -1:
            return -1
        right_height = self._isBalanced(root.right)
        if right_height == -1:
            return -1
        if abs(left_height - right_height) > 1:
            return -1
        return max(left_height, right_height) + 1
        

102. Binary Tree Level Order Traversal

Three compact python solutions

def levelOrder(self, root): 
    ans, level = [], [root] 
    while root and level: 
        ans.append([node.val for node in level]) 
        LRpair = [(node.left, node.right) for node in level] 
        level = [leaf for LR in LRpair for leaf in LR if leaf] 
    return ans

This is equivalent to:

def levelOrder(self, root): 
    if not root: 
        return [] 
    ans, level = [], [root] 
    while level: 
        ans.append([node.val for node in level]) 
        temp = [] 
        # this additional step is to make sure we only add valid (not None) leaf to level. 
        # In graph BST, we assume there won't be such None connection, therefore no need this examination
        for node in level: 
            temp.extend([node.left, node.right]) 
        level = [leaf for leaf in temp if leaf] 
    return ans

This cpp solution is more elegant.

vector<vector<int>> ret;
void buildVector(TreeNode *root, int depth) { 
    if(root == NULL) return; 
    if(ret.size() == depth) 
      ret.push_back(vector<int>());
    ret[depth].push_back(root->val); 
    buildVector(root->left, depth + 1); 
    buildVector(root->right, depth + 1);
  }
  vector<vector<int> > levelOrder(TreeNode *root) { 
    buildVector(root, 0); 
    return ret;
  }

There is other solution which use a queue. Also check them !!

98. Validate Binary Search Tree

def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')): 
    if not root: return True # this is necessary for each isValidBST call
      # it makes sure that the following root.val valid
"""
for tree related questions:
should we always include this 'if not root' check in recursion's base case? 
how is this related with return result? if return is connected by or / and,
how is the result gonna to be different? 
"""
    if root.val <= largerThan or root.val >= lessThan: 
        return False 
    return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and \\
self.isValidBST(root.right, lessThan, max(root.val, largerThan))

Python version based on inorder traversal

class Solution(object):
    def isValidBST(self, root):  
        self.res = list() 
        self.validation(root) 
        return self.res == sorted(self.res) and len(set(self.res)) == len(self.res)

    def validation(self, root): 
        if not root: 
            return 
        else: 
            self.validation(root.left) 
            self.res.append(root.val) 
            self.validation(root.right)

112. Path Sum

def hasPathSum(self, root, sum): 
    if not root: return False # this checking is needed at each call
        # return False also align with final OR return statement 
    if not root.left and not root.right and root.val == sum: 
        return True 
    sum -= root.val 
    return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

257. Binary Tree Paths

learn nested list comprehension in this example:

def binaryTreePaths(self, root): 
    if not root: 
        return [] 
    return [str(root.val) + '->' + path for kid in (root.left, root.right) if kid for path in self.binaryTreePaths(kid)] or [str(root.val)]
# NOTE: understand how nested list comprehension works !! 

Another solution (recursion):

def binaryTreePaths(self, root): 
    if not root: return [] 
    if not root.left and not root.right: 
        return [str(root.val)] 
    treepaths = [str(root.val)+'->'+path for path in self.binaryTreePaths(root.left)] 
    treepaths += [str(root.val)+'->'+path for path in self.binaryTreePaths(root.right)] 
    return treepaths

Python solutions (dfs+stack, bfs+queue, dfs recursively).

• It is extremely important to actually draw the stack and see what's going.
• It is also important to write out while loop and make good book keeping, when we think about such process.
• This is a good example shows how to modify the basic DFS/BFS to complete more complicated task
• It is particular important to notice that how we store extra information in stack/queue to complete our goal. It requires careful design to store the right information
• In this case, the right complimentary information stored in stack for each node is the complete path from root to this node
• The intuitive way that BFS/DFS can be tailored to complete this task is because, essentially, this task is about tree traversal. Therefore, we must be able to tailored tree traversal algorithm to handle this task.

# dfs + stack
def binaryTreePaths1(self, root):
    if not root:
        return []
    res, stack = [], [(root, "")] # basic setup
    while stack:
        node, ls = stack.pop() # for each call, initially, it will pop: node=root, ls=""
        if not node.left and not node.right:
            # means we reach leaf, and complete the path
            # append the path into res
            res.append(ls+str(node.val))
        if node.right:
            # path is not completed yet, continue to traversal deeper
            stack.append((node.right, ls+str(node.val)+"->"))
            # notice that how we store additional information in stack
            # the order of left/right doesn't matter. 
            # BFS/DFS don't matter neither. 
        if node.left:
            stack.append((node.left, ls+str(node.val)+"->"))
    return res

# bfs + queue
def binaryTreePaths2(self, root):
    if not root:
        return []
    res, queue = [], [(root, "")]
    while queue:
        node, ls = queue.pop(0)
        if not node.left and not node.right:
            res.append(ls+str(node.val))
        if node.left:
            queue.append((node.left, ls+str(node.val)+"->"))
        if node.right:
            queue.append((node.right, ls+str(node.val)+"->"))
    return res

129. Sum Root to Leaf Numbers

Python solutions (dfs+stack, bfs+queue, dfs recursively)

# Sol1: dfs + stackdef 
sumNumbers1(self, root): 
    if not root: return 0 
    stack, res = [(root, root.val)], 0 
    while stack: 
        node, value = stack.pop() 
        if node: 
            if not node.left and not node.right: 
                res += value 
            if node.right: 
                stack.append((node.right, value*10+node.right.val)) 
            if node.left: 
                stack.append((node.left, value*10+node.left.val)) 
    return res

# Sol2: bfs + queuedef
sumNumbers2(self, root): 
    if not root: return 0 
    queue, res = collections.deque([(root, root.val)]), 0 
    while queue: 
        node, value = queue.popleft() 
        if node: 
            if not node.left and not node.right: 
                res += value 
            if node.left: 
                queue.append((node.left, value*10+node.left.val)) 
            if node.right: 
                queue.append((node.right, value*10+node.right.val)) 
    return res

# Sol3: recursively 
def sumNumbers(self, root): 
    self.res = 0 
    self.dfs(root, 0) 
    return self.res

def dfs(self, root, value): 
    if root: 
        #if not root.left and not root.right: 
        # self.res += value*10 + root.val 
        self.dfs(root.left, value*10+root.val) 
        #if not root.left and not root.right: 
        # self.res += value*10 + root.val 
        self.dfs(root.right, value*10+root.val) 
        if not root.left and not root.right: 
            self.res += value*10 + root.val

100. Same Tree

def isSameTree1(self, p, q): 
    if p and q: 
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) 
    else: 
        return p == q

# DFS with stack 
def isSameTree2(self, p, q): 
    stack = [(p, q)] 
    while stack: 
        node1, node2 = stack.pop() 
        if not node1 and not node2: 
            continue 
        elif None in [node1, node2]: 
            return False 
        else: 
            if node1.val != node2.val: 
                return False 
            stack.append((node1.right, node2.right)) 
            stack.append((node1.left, node2.left)) 
    return True

# BFS with queue 
def isSameTree3(self, p, q): 
    queue = [(p, q)] 
    while queue: 
        node1, node2 = queue.pop(0) 
        if not node1 and not node2: 
            continue 
        elif None in [node1, node2]: 
            return False 
        else: 
            if node1.val != node2.val: 
                return False 
            queue.append((node1.left, node2.left)) 
            queue.append((node1.right, node2.right)) 
    return True

Questions with Medium Difficulty:

114. Flatten Binary Tree to Linked List

class Solution: 
    # @param {TreeNode} root 
    # @return {void} Do not return anything, modify root in-place instead. 

    def flatten(self, root): 
        ''' 1. flatten left subtree 
            2. find left subtree's tail 
            3. set root's left to None, root's right to root'left, tail's right to root.right 
            4. flatten the original right subtree ''' 
        # escape condition 
        if not root: 
            return 
        right = root.right 
        if root.left: 
            # flatten left subtree 
            self.flatten(root.left) 
            # find the tail of left subtree 
            tail = root.left 
            while tail.right: 
                tail = tail.right 
                # left <-- None, right <-- left, tail's right <- right 
            root.left, root.right, tail.right = None, root.left, right 
        # flatten right subtree 
        self.flatten(right)

105. Construct Binary Tree from Preorder and Inorder Traversal

# it is important to write python style code !! 
def buildTree(self, preorder, inorder): 
'''
this is a very elegant solution. The order of left and right is CRUCIAL!! 
based on the idea of DFS, the recursion will go to the deepest left, 
which will pop all left side pre-order list node, 
and therefore the right side can work! 
'''
    if inorder: 
        ind = inorder.index(preorder.pop(0)) 
        root = TreeNode(inorder[ind]) 
        root.left = self.buildTree(preorder, inorder[0:ind]) 
        root.right = self.buildTree(preorder, inorder[ind+1:]) 
        return root

106. Construct Binary Tree from Inorder and Postorder Traversal

def buildTree(self, inorder, postorder): 
    if inorder: 
        ind = inorder.index(postorder.pop()) # this is the difference !! 
        root = TreeNode(inorder[ind]) 
        root.right = self.buildTree(inorder[ind+1:], postorder) # this order should be changed!! 
        root.left = self.buildTree(inorder[:ind], postorder) 
        return root

another solution, claim to use less memory

108. Convert Sorted Array to Binary Search Tree

see discussion about pass list and memory consumption here
Hello, maybe this is not perfect place to ask this question. But I am very curious whether we are allowed use a copy of lists in these recursive functions in the interview (num[:mid] and num[mid+1:] are actually creating extra sublists). It works for this problem well but for problems like Construct Binary Tree From Preorder AndInoderTraversal, when I used similar method which is very straightforwad , it works locally but OJ gives memory limit exceed. Later I solved it by dealing with indexes instead of passing copy of lists(300+ms) and improved it with the help of hash table(70+ms) but it took me long time. I hope to use the first solution if possible since we don't have much time.

def sortedArrayToBST(self, num): 
    if not num: return None 
    mid = len(num) // 2 
    root = TreeNode(num[mid]) 
    root.left = self.sortedArrayToBST(num[:mid]) 
    root.right = self.sortedArrayToBST(num[mid+1:]) 
    return root