Why tree problems

Tree/graph traversal is a very important technique to know not only for interviews but also a lot of real world problems.

Chess and other board game

Trees can naturally represent the board states. The children of each node is the potential moves one player can make. IBM deep blue uses tree search to beat Garry Kasparov. (It also uses alpha-beta pruning and other techniques to cut down search time)

Decision trees

A classifier that could learn non-linear decision boundary. One of the best algorithm out there is C4.5 algorithm. Go check them out

The file system

There is a reason why the root is called root lol.

DOM and XML

We often need to find paths in XML. That’s when tree algorithms came in handy.

Tree is a class of graph and graph is great

A lot of really hard problems can be turned into graph problems and be solved more easily.

Types of tree

Binary tree

Where each node can have at most 2 children

Binary search tree

Binary tree is a tree where each node can have at most two children. Elements of the subtree rooted at left child must ALL be smaller than the root’s value. Elements of the subtree rooted at the right must All be larger than the root’s value. Could use binary search.

AVL and red-black tree(balanced search tree)

Tree search can have a problem when we have a tree that only grows on one side. Then the tree search will be O(n) instead of O(logn). We can balance the elements when constructing. These two are balanced search tree. CLRS has a chapter about red-black… Maybe be back later… BTW Linux Kernel uses red-black for job scheduling. A post online DAT POST

Traversal

three kinds of order

Preorder

We will visit/display the root of the tree first. Then we will visit/display the left side of the tree, then at last we visit/display the right. It is top down and is often used to copy trees. It is also used to make prefix expression such as polish expression

<br />        def recurse(root, sol):
            if root == None:
                return 
            sol.append(root.val)
            recurse(root.left, sol)
            recurse(root.right, sol)


        sol = []
        recurse(root, sol)
        return sol

Recursive way is easy to understood. If we reached a null node, just return. else we will first visit/check the parent then go to left then right.

    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        iter way
        """
        if root == None:
            return []
        stack = []
        sol = []
        stack.append(root)
        while stack:
            curr_root = stack.pop()
            if curr_root:
                sol.append(curr_root.val)
                stack.append(curr_root.right)
                stack.append(curr_root.left)

        return sol

Iterative method uses an aux data structure: stack. It will hold the node to be visited next. We push the root into it and loop till the stack is empty. In the loop it will pop off the node, visit it and then push right side first. Because we want to visit right side last and we are using stack, which is FILO, we will put the right first.

This in effect make sure we visit all the nodes on the root andleft before we visit any right node.

inorder

We will visit/display the left, then the root and the right. It is used to “flatten” the tree, squeezing the middle between the left and right. Binary search tree use it to return the order.

def inorder(root, sol):
    if not root:
        return 
    inorder(root.left, sol)
    sol.append(root.val)
    inorder(root.right, sol)

Just to clarify, when we are at a leaf node, we inorder will call inorder(leaf.left), which will just return. Then it will put its value on to sol and last call inorder(leaf.right) which also return none. So this function can handle leaf nodes.

def inorder_iter(root):
    sol = []
    stack = []
    curr = root
    while curr or stack:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            sol.append(curr.val)
            curr = curr.right
    return sol

The iterative method imitates the recursive method that goes all the way to the left by storing the parents node to a stack. It will go all the way till the left most element and pushing all of them on the the stack first. Then it will try to go to its left, which is null and would pop the left most child off the stack. We will put that child’s value into the solution and try to go to its right. If it doesn’t have any right child, then we will pop again, which will give us the parents of the left most node. This will go on until the stack is empty and curr points to null.

We have a variable called curr that points to the node we are currently examine. Since we only pop when we reached the left-most of a tree, we can’t use the poped value to traverse tree. Also imagine what if the tree is one-sided where every node is bigger than its parent. Then the stack would be always empty and we need to use curr to iter through the tree.

There is also another method called Morris method and it uses Threaded binary tree. Morris method

Postorder

Visit the left right children before the parents. This is Bottom up and is good for deleting subtree rooted at a node(so we won’t lose the parents before the children are deleted . It could also generate postfix expression.(with a stack)

#We will use stack to store note only the node but visit info.
#Only when the visit flag is true will we store the value into sol

def post_traversal(root):
    stack = [(root, False)]
    sol = []
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                sol.append(node.val)
            else:
                stack.append(node)
                stack.append(node.right)
                stack.append(node.left)  #Put left last since we want to go there next

    return sol

Problems to solve

Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Binary Tree Zigzag Level Order Traversal
Average of Levels in Binary Tree
Binary Tree Right Side View
Find Largest Value in Each Tree Row
Populating Next Right Pointers in Each Node

Symmetric tree

<br />        def sym_recurse(root_left, root_right):
            """
            return if the subtree under the two nodes are symmetric.
            start with both root and root
            """
            if not root_left and not root_right:
                return True

            elif not root_left or not root_right:
                return False 
            else:
                outer_result = sym_recurse(root_left.left, root_right.right)
                inner_result = sym_recurse(root_left.right, root_right.left)
                return root_left.val == root_right.val and outer_result and inner_result

        return sym_recurse(root, root)

The sym_recurse function will return whether the subtree rooted at root_left and root_right are symmetric. Two subtrees are symmetric if the root nodes’ value match and also the the left subtree of left matches the right subtree of the right. The base case is when both nodes are None. It is vacuously Tree.

The tricky part is to start, we need to pass root as argument. That means we want to find out if the sub tree on the left of root is equal to the subtree on the right of the root.

Number of uni value subtrees

<br />        def recurse_visit(root):
            """
            Use post ordre traversal to visit the child first
            Return True if the tree rooted at root is a valid univalue subtree
            """
            if not root:
                return True
            left = recurse_visit(root.left)
            right = recurse_visit(root.right)

            if left and right:
                if (not root.left or root.left.val == root.val) and (not root.right or root.right.val == root.val):
                    self.tree_num += 1
                    return True
            else:
                return False

        if not root:
            return self.tree_num
        recurse_visit(root)
        return self.tree_num

This question ask us to find the number of uni value subtrees. A unival subtree is a tree that all values are the same.

In the tree we have 4 subtrees. the three leaf nodes. and the second 5 nodes from the leaf is also a valid unival subtree. The top node 5 is not a unival subtree because the left side’s node is not equal to 5.(we can’t slice the tree up(no 5-5-5).

To solve this problem, we resort to bottom-up method to traverse the tree. We noticed that any leaf node is itself a univalue tree. Any internal would be a root of a unival subtree if both left and right children are uni value subtree and the node’s value match with that of the children.

Our function recurse_visit(root) will return True if the tree rooted at root is a uni value tree. It is vacuously true when root is None. Then it will call recurse_visit on both left and right, implementing the post order traversal. Then two calls will return if the left and right side are uni value subtree. If they both are and the left and right values are equal to that of the root, then the root is a root for a unival subtree as well and we increment the counter by one.

Observations

How to represent a tree?

Array

Linkedlist

Bottom up or top down

This leetcode tutorial is super good at explaining this concept. It gave a formula to solve tree problems using recursion.

Topdown

In topdown, we first visit the root node, calculate some value, then pass that value further down to its children. Then we the children reach the leaves, they might alter some global variables to store the result. It is kind of Preorder traversal

return specific value for null node
update the answer if needed // anwer <– params
left_ans = top_down(root.left, left_params) // left_params <– root.val, params
right_ans = top_down(root.right, right_params) // right_params <– root.val, params
return the answer if needed // answer <– left_ans, right_ans

A problem can be solved using top down if the result of the parent node can infer the result of the child node. EG in maximum depth of a tree, if we know the depth of the parent d, then the depth of its children will be d + 1.

return if root is null
if root is a leaf node:
answer = max(answer, depth) // update the answer if needed
maximum_depth(root.left, depth + 1) // call the function recursively for left child
maximum_depth(root.right, depth + 1) // call the function recursively for right child

Notice there is no return return is used to break out of the base case

Bottom up

Another method is bottom up where the result of the parent node can be found by the results of the children nodes. We will first recursively call all children and use the return values of the children to EG if we know the max depth of the children of a node, the the max depth of the node would be the max of max depth + 1.

return 0 if root is null // return 0 for null node
left_depth = maximum_depth(root.left)
right_depth = maximum_depth(root.right)
return max(left_depth, right_depth) + 1 // return depth of the subtree rooted at root

Tree problems