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
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.
5
/ \
1 5
/ \ \
5 5 5
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