trees_graphs

Trees & Graphs

Tree common algorithms

Tree Height

• 104. Maximum Depth of Binary Tree
• 110. Balanced Binary Tree
• 543. Diameter of Binary Tree

Binary Tree Traversal

Different traversal order

In-order

left -> root -> right

Python

Pre-order

root -> left -> right

Derived DFS.

Python

Post-order

left -> right -> root

Derived DFS.

Python

Level Order

Traverse the tree one layer at a time

     3
    / \
   9  20
     /  \
    15   7
------------
[
    [3],
    [9, 20],
    [15, 7]
]

This is similar to Bread-first Search. The trick is to use a queue, and iterate the length of the queue to store each layer node.

Python

Graph Search

Bread-first Search (BFS)

Python

Depth-first Search (DFS)

Python