Tree Key Point Review

Tree is an important data structure.
There are multiple ways to implement, today we are going to talk about the most common 2 ways.

Implementation

HashMap

Hash map implementation is useful when given edges instead of a tree structure.
For example, if given edges: [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
We can convert edges into a hash map like this:

1
2
3
4
5
6
7
8
{
    0: [3],
    1: [3],
    2: [3],
    3: [0, 1, 2, 4],
    4: [3, 5],
    5: [4]
}

Simply iterate through the edges and create this table:

1
2
3
4
5
6
from collections import defaultdict

graph = defaultdict(list)
for e in edges:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

TreeNode Class

While the previos one is useful for all kinds of graph, this implemention is only useful for binary (or n-ary) trees, because the children number has to be fixed. 

1
2
3
4
class TreeNode:
    def __init__(self, val, l=None, r=None):
        self.val = val
        self.left, self.right = l, r

Operations and Time Complexity

To search or insert a node, the time complexity is O(h), where h is the height of the tree. The height is also at least O(logn).
Because this is not very efficien, we later introduce AVL Tree and Red-Black Tree.
To delete a node is less straightforward, because there are multiple cases.
If the node is a leaf, we simple delete it; if it has one child, we bypass the child. However, if there are 2 children, we replace the value with the largest value in its left subtree, and then delete that node.
This is to prevent the tree from breaking into 2 subtrees without access to one of them.

DFS

DFS, depth first search, is useful when finding paths or connected compartment.
There are 2 different kinds of implementation: recursive and iterative. 

1
2
3
4
5
6
7
# This code uses the 2nd implementation of tree above 
# and assume that it's a binary tree
def DFS(node):
    if not node.left and not node.right:
        return
    DFS(node.left)
    DFS(node.right)

The non-recursive, or iterative way utilize a stack.

1
2
3
4
5
6
7
8
9
# This code uses the 1st implementation of tree above
stack = [root]
visit = []
while len(stack) > 0:
    node = stack.pop()
    visit.append(node)
    for n in graph[node]:
        if n not in visit:
            stack.append(n)

Inorder, preorder and postorder are 3 ways of DFS.

  • PreOrder traversal - visit the parent first and then left and right children;
  • InOrder traversal - visit the left child, then the parent and the right child;
  • PostOrder traversal - visit left child, then the right child and then the parent;

There are multiple ways, I’m only going to write some.

Preorder , recursion with side effects: 

1
2
3
4
5
6
7
8
def preorder(root):
    if root == None: return

    visit.append(root.val)
    preorder(root.left)
    preorder(root.right)

    return

Inorder, recursion without side effects:

1
2
3
4
def inorder(root, visit):
        if root == None: 
            return visit
        return inorder(root.left, visit) + [root.val] + inorder(root.right, visit)

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def inorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    res, stack = [], []
    while True:
        while root:
            stack.append(root)
            root = root.left
        if not stack:
            return res
        node = stack.pop()
        res.append(node.val)
        root = node.right

Binary Tree Postorder Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def postorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    res = []
    stack = [root]
    if not root: return []
    while len(stack) > 0:
        node = stack.pop()
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
        res.append(node.val)
    return res[::-1]

BFS

BFS, or Breadth First Search, is useful when finding shortest path.
The biggest difference is that instead of stack in DFS, BFS uses a queue.

1
2
3
4
5
6
7
8
9
# This code uses the 1st implementation of tree above
queue = [root]
visit = []
while len(queue) > 0:
    node = queue.pop(0)
    visit.append(node)
    for n in graph[node]:
        if n not in visit:
            queue.append(n)

We can easily modify the code to find depth and path to a specific node. 

1
2
3
4
5
6
7
8
9
10
q = [(node, 1, [node])]
visit = []
depth = 0
while len(q) > 0:
    node, d, path = q.pop(0)
    if node == goal: break
    visit.append(node)
    for n in graph[node]:
        if n not in visit:
            q.append((n, d + 1, path + [n]))

Balanced

Balance meaning the height of every left and right subtree cannot differ more than 1.
We can check it recursively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isBalanced(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    def check_height(root):
        if not root: return 0
        left_height = check_height(root.left)
        right_height = check_height(root.right)
        if left_height == -1 or right_height == -1:
            return -1
        if abs(left_height - right_height) > 1: return -1
        return max(left_height, right_height) + 1

    return check_height(root) != -1

Trie (Prefix Tree)