Chapter 1 - Trees

Question 1

Lowest Common Ancestor in a tree - Given a tree and two nodes p and q, find LCA of them

Answer 1

# if p in q or q in p -> then either of them is the LWA
        # if p is node.left and q is node.right -> node is LWA
        # if root of p -> if q is in root -> root is LWA
        # elif root of q -> if p is in root -> root is LWA
	# else -> rerun LWA on p_root and q_root

Question 2

Sum of nodes in BST b/w L and R (Range sum of BST)

Answer 2

DFS ->
Recursive over each node, compare the value of each node with L, R

    def rangeSumBST(self, root, L, R):
        ans = 0
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if L <= node.val <= R:
                    ans += node.val
                if L < node.val:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
        return ans

Question 3

Serialize Binary Tree

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as “[1,2,3,null,null,4,5]”

Answer 3

We start from the root, node 1, the serialization string is 1,. Then we jump to its left subtree with the root node 2, and the serialization string becomes 1,2,. Now starting from node 2, we visit its left node 3 (1,2,3,None,None,) and right node 4 (1,2,3,None,None,4,None,None) sequentially.
Finally, the serialization string is done as 1,2,3,None,None,4,None,None,5,None,None,

# Serialization 
class Codec:

def serialize(self, root):
    """ Encodes a tree to a single string.
    :type root: TreeNode
    :rtype: str
    """
    def rserialize(root, string):
        """ a recursive helper function for the serialize() function."""
        # check base case
        if root is None:
            string += 'None,'
        else:
            string += str(root.val) + ','
            string = rserialize(root.left, string)
            string = rserialize(root.right, string)
        return string

    return rserialize(root, '')

Complexity: O(n) and O(n)

Question 4

DeSerialize Binary Tree

Answer 4

Deserialize the serialization string constructed above 1,2,3,None,None,4,None,None,5,None,None,. It goes along the string, initiate the node value and then calls itself to construct its left and right child nodes.

# Deserialization 
class Codec:

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def rdeserialize(l):
            """ a recursive helper function for deserialization."""
            if l[0] == 'None':
                l.pop(0)
                return None

            root = TreeNode(l[0])
            l.pop(0)
            root.left = rdeserialize(l)
            root.right = rdeserialize(l)
            return root

    data_list = data.split(',')
    root = rdeserialize(data_list)
    return root

Complexity: O(n) and O(n)

Question 5

Validate BST

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contains only nodes with keys greater than the node’s key.

Both the left and right subtrees must also be binary search trees.

Answer 5

Condition 1:
Left node should be smaller than the root.
Right node should be greater than the root.

Condition 2:
There will be upper and lower limit for each node.
Not only the child on left subtree should be smaller than the node but all the elements in the left subtree.
Not only the child on right subtree should be larger than the node but all the elements in the right subtree.

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(node, lower = float('-inf'), upper = float('inf')):
            if not node:
                return True

        val = node.val
        if val <= lower or val >= upper:
            return False

        if not helper(node.right, val, upper):
            return False
        if not helper(node.left, lower, val):
            return False
        return True

    return helper(root)

Complexity: O(n) and O(n)