Tree

Posted on Edited on In ,

Tree is a basic data structure. The most popular tree is the binary tree, which has a left child and a right child. The exercise usually gives you the root node of the tree. The basic method to solve a tree problem is recursive.

Traverse the tree

Iteration

1
2
3
4
5
6
openlist = [root]
while len(openlist) > 0:
    node = openlist.pop()	# openlist.pop(0) if you want BFS 
    check(node) 
    openlist.append(node.left)
    openlist.append(node.right)

Recursive

1
2
3
4
def check_tree(node):
    if node:
        check_tree(node.left)
        check_tree(node.right)

The above two ara both DFS(Deep First Search), in order to achieve the BFS(Breadth First Search), in other means, traverse the tree layer by layer, we need to use a dictionary to store the node

1
2
3
4
5
6
7
8
9
10
dic_tree = {}

def check_tree_breadth(node, depth=1):
    if node:
        if depth not in dic_tree:
            dic_tree[depth] = [node.val]
        else:
            dic_tree[depth].append(node.val)
        check_tree_breadth(node.left, depth+1)
        check_tree_breadth(node.right, depth+1)

Check the leaf

1
2
3
4
5
6
7
8
9
leafs = []

def check_leaf(node):
    if node:
        if not node.left and not node.right:
            leafs.append(node.val)
        else:
            check_leaf(node.left)
            check_leaf(node.right)

Calculate the depth

Iteration

Establish a list to collect the tuple like (node: depth)

Recursive

1
2
3
4
5
def get_depth(node):
    if node:
        return 1 + max(get_depth(node.left), get_depth(node.right))
    else:
        return 0

Check the path

1
2
3
4
5
6
7
8
9
paths = []

def check_path(node, path=[]):
    if node:
        path.append(node.val)
        check_path(node.left, path.copy())
        check_path(node.right, path.copy())
    else:
        paths.append(path)