System Design: Twitter

Standard for evaluation

可行解 Work Solution 25%

特定问题 Special Case 20%

分析能力 Analysis 25%

权衡 Tradeoff 15%

知识储备 Knowledge Base 15%

4S analysis

Scenario

1. Features: list all the features and sort them by priority
2. DAU -> QPS: based on daily active user (DAU), calculate the query per second (QPS, read QPS, write QPS), including avg QPS and peak QPS (usually about 2 or 3 times of avg QPS)
   • DAU: assuming ~100M
   • QPS: DAU * query estimation per day / 86400 (Note:86400s = 24h)
     QPS = 100M*5/86400
3. Interfaces

Service: design the service based on QPS

1. Split the system into several subsystems

Storage

1. How to store/access data:  SQL / NoSQL / File System
   • SQL: transaction, complex table with multiple columns
   • NoSQL: graph relationship (e.g., friendship)
   • File System: picture, video, etc.
2. Schema: details the table structure

Scale

1. Sharding / Optimize / Special Case

Design Twitter

1. Scenario:
   • Register / Login
   • User Profile Display / Edit
   • Upload Image / Video
   • Search
   • Post / Share a tweet*
   • Timeline / News Feed*
   • Follow / Unfollow a user*
2. Service
   • User service: register/login/user profile display/edit
   • Search service: search
   • Media service: upload image/video
   • Tweet service: post/share/timeline/newsfeed
   • Friendship service: follow/unfollow
3. Storage:

Decide where to store:

• User service: SQL
• Search service: index -> File System
• Media service: File System
• Tweet service: NoSQL (tweet content -> NoSQL)
• Friendship service: NoSQL (it is also OK to put it in SQL, but NoSQL is better)

Details the schema of the table

READ MORE: when to use SQL/NoSQL????

Details the service

Tweet service: post/share/timeline/newsfeed

Friendship service: follow/unfollow

1.How to store and get "News Feed"

1)Pull Model

    [Idea] Once the user checks his news feed, pull all followings’ timelines and merge them.

    [Process]

    [Problem] We need to do n times DB read (n = # of followings), which is very slow and not acceptable.

    [Solution] Cache all user’s timeline (memcached)

    [Follow Up]: Thundering herd problem: millions requests coming in at once, the DB and server cannot handle it.   

    [Solution] https://code.facebook.com/posts/1653074404941839/under-the-hood-broadcasting-live-video-to-millions/

    [Follow Up]: 点赞,转发,评论,都会修改这条 Tweet 的基本信息,如何更新? •

    [Solution] Keywords: write through, write back, look aside

    [Follow Up]: Cache 失效如何破? 因为内存不够或者Cache决策错误,热点信息被踢出了Cache,会发生什么? 

一大波僵尸袭来——DB会瞬间收到一大波对该数据请求,然后就可以安心的挂了

    [Solution] Facebook Lease Get(from Facebook Paper) • Read more: http://bit.ly/1jDzKZK

2)Push Model

    [Idea] Once a user posts a new tweet, push this tweet to all his follower’s newsfeed.

    [Process] 

    [Problem] A lot of followers problem: If the following has hundreds of thousands of followers, this process will take a very long time and the user might not be able to see his/her post until several days later. 

    [Solution] For the following who owns a huge number of fans, when his/her fans check newsfeed, use pull model to update the newsfeed. But do not write the following’s timeline into follower’s newsfeed. Let push model to finish this part.

同类型的类似问题

Design Facebook

Design Instagram

Design Friend Circle (朋友圈)

Design Google Reader(RSS Reader)

课后作业:对比MySQL 和 Memcached 的 QPS • Memcached QPS / MySQL QPS ~ 100

How to check mutual friends 

Related Reading:
Scaling Twitter: Making Twitter 10000 Percent Faster

How Twitter Uses NoSQL

NoSQL DB Comparation

Decomposing Twitter (Database Perspective)

COLLECTING TWITTER DATA: STORING TWEETS IN MONGODB

How Twitter Stores 250 Million Tweets A Day Using MySQL
Compare NoSQL DB:

https://www.digitalocean.com/community/tutorials/a-comparison-of-nosql-database-management-systems-and-models

Advance Tree Algorithm 1 Summary - Leetcode

1. Serialization

[Method 1] pre-order+in-order or in-order+post-order
[Problem] same nodes will cause problems in deserialization.
e.g., pre-oder = [5,5,5,5], in-order = [5,5,5,5] ->no way to figure out what exactly the tree looks like.

[Method 2] level-order serialization
    

[1,2,3,4,null,5,6,null,null,null,null]

(You can also trim all the "null" in the end)

    

2. Binary Search Tree 

1. Predecessor and Successor

java.util.TreeMap support API ceiling(value) and floor(value)
[Question]
270. Closest Binary Search Tree Value

2. other BST questions

222. Count Complete Tree Nodes
230. Kth Smallest Element in a BST

Compare DFS and BFS

BFS Summary - Leetcode

0.Basic Concepts

Breadth First Search (BFS) is a method for traversing or searching tree or graph data structures.

1.When do we apply BFS?

It is frequently used to
  1) explore some features/characteristics in the tree/graph.
     [typical examples]
        [101] Symmetric Tree
        [261] Graph Valid Tree

  2) search for nodes/level/connected components
     [typical examples] search for nodes/connected components
        [133] Clone Graph
        [200] Number of Islands
        [323] Number of Connected Components in an Undirected Graph
        [286] Walls and Gates

     [typical examples] level related problem
        [102] Binary Tree Level Order Traversal
        [103] Binary Tree Zigzag Level Order Traversal
        [107] Binary Tree Level Order Traversal II
        [199] Binary Tree Right Side View

  3) shortest steps(path) 

     Utilizing BFS to find the shortest path involves a lot of details, so let's use an example to discuss it.

Example:

The solution needs to:

1)Utilize a matrix (int[][] distance) to record the shortest distance from node A to node (i, j). If we cannot reach the node (i, j), marked it as -1. 

2)Apply BFS to calc distance[][]. All distance[i][j] except the the start point should be initialized as -1; the start point distance is initialized as 0.

3)When updating the distance matrix using BFS, for each dequeued node, we will enqueue its unvisited grass neighbor (which means distance of an obstacle will always be -1. This also makes sense because -1 means unreachable):

Here we show the pseudo codes for this BFS process (which is also classical BFS codes):

Follow-up 1:

What if we can move in 8 directions? (up, upright, right, ...)

If you run the above code, you will meet a bug like this:

Why?

In the round 0, you dequeue A, and enqueue all nodes around A, which are (0,0), (0,1), (1,1), (2,1), (2,0)

In the round 1, you first dequeue (0,0), as we can see, for (0,0), its unvisited neighbors are (0,1), (1,1), so you will enqueue these two nodes.

This means in the round 2, you will pop (0,1) and (1,1) again, and set their distances value as 2.

Now we see our problem:

If the nodes in the queue can be each other’s neighbors, the neighbor can be added to the queue again, which will cause wrong distance.

How to solve it?

distance[i][j] == -1 means this node is unvisited. So before we update node (i,j)’s distance value, check whether distance[i][j] == -1

So we new code is:

Follow-up 2:

If we want to find the minimum path, rather than only find the minimum steps to from one node to another, how to achieve this?
There are two ways:

1. We can store Tuple<Node, Path> into the queue. -> O(n^2)

2. We can use BFS to find how long is the shortest path (assume k). Then we apply DFS to find the path (because we know path length = k, for a path longer than k, we can stop earlier). -> O(n), but DFS has stack overflow problem.

[typical questions]
        [111] Minimum Depth of Binary Tree
        [126] Word Ladder II
        [310] Minimum Height Trees

        [317] Shortest Distance from All Buildings

Object Oriented Design - Lecture 3: Use Cases

This post is the note of lecture 2 of the course "Object Oriented System Analysis and Design". Videos can be viewed at https://www.youtube.com/watch?v=ODeQ0rF59kI&index=3&list=PL6XklZATqYx9dj72MKG6wLYjljeB2odra.

Lecture 3

1.Use cases definition

1. Definition: use case is an activity that system performs, usually in response to a request by a user.
2. Use cases define functional requirements.
3. Two techniques to identify use cases:
1. user goal technique
2. event decomposition

2.User goal technique

Seldom use. 

3.Event decomposition technique

1. Type of Events
1. external event: an event that occurs outside the system, usually initialized by an external agent/actor.
2. internal event:
1. temporal event: ana event that occurs as a result of reaching a point in time (e.g., 
2. The decomposition process:
1. Identify the event that occurs to which the system must respond.
2. For each event name a use case (verb-noun) that describes what the system should do
3. CRUD decomposition: Create, Read/Report, Update, Delete
   Steps:
1. Identify all domain classes (e.g., Customer, Seller, etc)
2. Check whether we need CRUD functions
3. When integrating applications, make sure it is clear which application is responsible for adding and maintaining the data, and which system merely uses the data.
3. Use case diagram

Object Oriented Design - Lecture 2: Strategic Planning and Related Design

This post is the note of lecture 2 of the course "Object Oriented System Analysis and Design". Videos can be viewed at https://www.youtube.com/watch?v=ODeQ0rF59kI&index=3&list=PL6XklZATqYx9dj72MKG6wLYjljeB2odra.

Lecture 2

1. Planning method - strategic planning

1. Definition of the technology architecture (infrastructure)
1. the set of computing hardware
2. network hardware/topology
3. system software employed by the organization
2. Application architecture
1. information system, subsystem, supporting technology
   e.g. update the RMO system due to customer expectation, modern technological capability, etc.
   [What we have]
1. Supply Chain Management System (SCM)
   (5 years old, Java/Oracle, tradeshow system will interface with SCM)
2. Phone/Mail Order System
   (12 years old, Visual Studio/MS SQL, reached capacity, minimal integration)
3. Retail Store System
   (order package solution, minimal integration)
4. Customer Support System (CSS)
   (web-based system, etc)
2. Information Diagram
   

2.Analysis, understand the details of the problem

1. Gather detailed information (interviews, questionnaires, etc.)
2. Define system requirements: modeling functional/non-functional requirements.
3. Prioritize requirements.
4. Develop user-interface dialogs.
5. Evaluate requirements with users.

 Define system requirements (FURPS+)

1. Functional requirements: APIs that should be implemented in the system.
2. Non-functional requirements:
1. Usability requirements: how easy it is to use the system (UI). (Need to consider whether the user can be trained.)
2. Reliability requirements: reliable for the day and night? or just day?
3. Performance requirements: response time, etc.
4. Secure requirements: encryption, etc.
5. + more other categories.

 Models and Modeling

1. After collecting information, create models which can be:
1. Textual models
2. Graphical models -  diagram, schematic
1. use case diagram
2. class diagram
3. sequence diagram
4. common diagram
5. state machine diagram
3. Mathematical models

Binary Search Summary - Leetcode

1.Definition

Binary Search is a search algorithm that finds the position of a target value within a sorted array (or an array arranged in a special way).

2.Methods

The key point of binary search is to maintain a range and make sure the target number is in the range. The search process is to shrink the range in multiple iterations until its size is 1 or find it.

In each iteration, half (or 1/n) the range's size. Use the middle element's value to decide it is the left half range or the right half range.

3 key steps:

1) identify the range (sometimes we might need to construct the range)

2) decide the appropriate way to shrink the range

3) check potential endless loops

e.g., find the index of 5 in the array 0-9

Note: We can use two pointers (lo, hi) to represent the range.

3.When do we apply binary search? 

1.Index-based search problem: 3 basic BS problems and corresponding methods to shrink the range. 

[question] Given a sorted array/matrix, try to find a specific element.

[identify the range] In this kind of question, the range is the index range [0, arr.length-1].

[methods of shrinking the range]

We will discuss how to shrink the range in the 3 types of BS problem. Let's assume that the current range is [lo, hi], and mid = lo+(hi-lo)/2.

[type 1] Find the only/any one problem

[Typical example]: find the index of 5 in the array [0,1,2,3,4,5,6]

[Explain]:

if array[mid] < target, shrink the range as [lo, mid-1];

else array[mid] > target, shrink the range as [mid+1, hi];

else return mid;

[Questions]

74. Search a 2D Matrix

240. Search a 2D Matrix II

374. Guess Number Higher or Lower

[type 2] Find the first one

[Typical example]: find the index of the first 5 in the array [0,1,1,1,2,3,4,5,5,6]

[Explain]:

if array[mid] == target, shrink the range as [lo, mid]; //*

else if array[mid] < target, shrink the range as [mid+1, hi];

else shrink the range as [lo, mid-1];

//* It is possible to trigger an endless loop. So we need to check whether lo==mid, if it is, break and jump out of the loop.

[Questions]

153 Find Minimum in Rotated Sorted Array

35 Search Insert Position

275. H-Index II

278. First Bad Version

[type 3] Find the last one

[Typical example]: find the index of the last 5 in the array [0,1,1,1,2,3,4,5,5,6]

[Explain]:

if array[mid] == target, shrink the range as [mid, hi];

else if array[mid] < target, shrink the range as [lo, mid-1];

else shrink the range as [mid+1, hi];

[type 4 - combination type] questions involves two or three types above

153 Find Minimum in Rotated Sorted Array

154. Find Minimum in Rotated Sorted Array II

33. Search in Rotated Sorted Array

81. Search in Rotated Sorted Array II

34. Search for a Range

2.Advanced binary search: shrink the range in a specific way

[calculation problem] 

[Identify the range]: given a number n, the range is [0,n]

tips: >>1 <<1 corresponds to /2, *2, which can be used in binary operations.

[questions]

367. Valid Perfect Square

29. Divide Two Integers

69 Sqrt(x)

50. Pow(x, n)

287. Find the Duplicate Number

[Other typical array/matrix related binary search problem]

302. Smallest Rectangle Enclosing Black Pixels

[key point]

1. [identify the range]: contstruct an array, array[i] represents in the column i of the matrix, there is at least one 1. the array will be like [00011111000].

2. [methods of shrinking the range]: find the first 1's and last 1's index.

354. Russian Doll Envelopes

4. Median of Two Sorted Arrays

1.[identify the range] the range contains two sorted array, [arr1] and [arr2]
2.[methods of shrinking the range]:
   

363. Max Sum of Rectangle No Larger Than K

162. Find Peak Element

[Other related questions]

300. Longest Increasing Subsequence

209. Minimum Size Subarray Sum

378. Kth Smallest Element in a Sorted Matrix

349. Intersection of Two Arrays

350. Intersection of Two Arrays II

Object Oriented Design - Lecture 1: Introduction to SDLC

This post is the note of lecture 1 of the course "Object Oriented System Analysis and Design". Videos can be viewed at https://www.youtube.com/watch?v=ODeQ0rF59kI&index=3&list=PL6XklZATqYx9dj72MKG6wLYjljeB2odra.

Lecture 1

1. System Design Methodology

1. System Design Lifecycle (SDLC)


1. Identify the problem and obtain approval
2. Plan the project
3. Understand the details of the problem or need
4. Design the system components (Draw a diagram)
5. Build, test, and integrate system components
6. Deploy the system

2. Actual approaches used to develop a particular information system

1. Unified process
2. Extreme programming
3. Scrum (suitable for team work)
4. Agile development (emphasizes flexibility to anticipate new requirement during development)

3.RMO example to illustrate SDLC

1. Need/requirement
1. Small information system
2. Being added to large supply chain management system
3. Demonstrate one iteration of the small project, assuming there are more
2. Look through all six phases in SDLC
1. Phase 1: Identify the problem
• Problem: purchasing agents attend appareal and fabric trade show around the whold to order new products from supplier.
• Need: build a new information system (app) to track information about supplier and new products while at trade show.
2. Phase 2: Plan 
• System vision document (problem description + system capability + business benefits).
• Work breakdown structure (tasks, whose responsibility, estimated working hours)
3. Phase 3: Analysis (understand the details of the problem or need)
• Basic ideas:   supplier subsystem + product subsystem
• Use cases (一般包括增删查改) + a use case diagram:
    Supplier: look up suppliers; enter/update/delete supplier information; look up contact; enter/update/delete contact information, etc
    Product: look up product information; enter/update/delete product information; upload product image, etc
• Information diagram (for supplier/product, what information we should have)
  
4. Phase 4: Design
• Design databases: table design, key-index identification, attribute types, referential integrity
  
• Design the system's high level structure: 
• Browser, window, smart phone
  
  
• Architectural configuration (components)
• Class diagram
  
• Subsystem architecture
  
5. Phase 5: Implementation
6. Phase 6: Maintenance

Advance Tree Algorithm 2 Summary - Leetcode

Union-Find with Path Compression

Problem Description: Find All Disjoint Sets

Idea:

1.Build roots array:

If we can build the root array as shown in the fig, we can find the root of a node. Two nodes belong to the same set if they share the same root.

(Note: The root's parent is the root itself. e.g., node 5's parent is node 1. Node 1's parent is node 0. Node 0's parent is 0. So node 0 is the root of node 5.) 

2.Path compression
Because we only care about the root of a node, so rather than store its parent, it is better to store its root in the array. To achieve this, we need to implement path compression.

Key Points:

1.Use Array to represent a tree/graph.
2.Path compression

A very good tutorial:
https://www.youtube.com/watch?v=ID00PMy0-vE

Basic Algorithm:

-------------------------------------------------------------
public union_find(int[] edges, int n){
  //n indicates node 0~node n-1
  int[] roots = new int[n];
  for(int i=0;i<n;i++) roots[i] = i;    //i indicates node i
    //use "int[] roots" to construct a tree. roots[i] represents node i's parent (root if using path compression)

  for(int[] edge: edges){
    int root1 = find(edge[0], roots);                        
    int root2 = find(edge[1], roots);                        
    if(root1!=root2) merge(root1, root2, roots);             
  }
}

private int find(int node, int[] roots){
  if(node==roots[node]) return node;
  else{
    roots[node] = find(roots[node],roots); //path compression
  }
return roots[node];
}

private void merge(int root1, int root2, int[] roots){
  roots[root1]=root2;
}

-------------------------------------------------------------
Questions:
[323] Number of Connected Components in an Undirected Graph
[261] Graph Valid Tree

Advanced

If nodes cannot be represented as 0,1,2,3 ... (a continuous sequence), we can use a map, giving each node an id.

Questions:
[128] Longest Consecutive Sequence

Topological Sorting

Problem Description

Input: a directed graph
Output: an ordered array of nodes. (Requirement: If there is an path (0->1) in the graph, the result array should put node 0 in front of 1.)

1.Topological sorting based on DFS

1)Idea

Start from any node and do DFS. When the node has not been visited yet, its status is 0. When the node is being visited (or its descent is being visited), the node's status is 1. When the node's all descent have been visited, the node's status is 2. And it is the time to put the node into the stack.

Considering the node's descents will always be put into stack before itself, the output ordered array is the sequence of the nodes in the stack from the top to the bottom.

2) How about the loop?

When you meet a node which is being visited (status = 1), what does it mean? YOU MEET A LOOP in the graph. Under such situations, there won't be a valid output. You might want to throw an exception now!

3) Key points

Hashmap: (int[] array) stores nodes' status.
Stack: stores the visited nodes.
DFS

4) Basic Algorithms

-----------------------------------------------------------
public int[] potologicalSort(int[][] edges, int n) throws Exception{
    //n indicates node 0~node n-1
    List<List<Integer>> graph = buildGraph(edges, n);
    int[] visited = new int[n];
    Stack<Integer> stack = new Stack<>();

    for(int i=0; i<n; i++){
        //If the node is in the loop (being visited)
        //If the node has not been visited, do dfs
        if(visited[i]==1) throw new Exception("There is a loop in the graph");
        else if(visited[i]==0) dfs(i, graph, visited, stack));
    }

    int[] result = new int[n];
    int i=0;
    while(i<n) result[i++]=stack.pop();
    return result;
}

private void dfs(int node, List<List<Integer>> graph, int[] visited, Stack<Integer> stack) throws Exception{
    visited[node] = 1;
    for(int i:graph.get(node)){
        //do dfs on all children of the node
        if(visited[i]==1) throw new Exception("There is a loop in the graph");
        else if(visited[i]==0) dfs(i, graph, visited, stack));
    }
    visited[node]=2;
    stack.push(node);
}

private List<List<Integer>> buildGraph(int[][] edges, int n){
//build the adjacency list of a graph
}
-----------------------------------------------------------

2.Topological sorting based on BFS

1) Idea

A node's fan-in: is the number of the node's parents (source node). e.g., in the graph, node 2's fan-in is 1, because it has a source node 0. Node 3'2 fan-in is 2 because it has 2 source nodes (node 1 and 2). Node A's fan-in = 0 means there is no node pointing to A.

The algorithm initializes the queue with all the node with fan-in=0. After we poll a node from queue, we update its children's fan-in table. Each child's fan-in -= 1. If the fan-in = 0, we add the child into the queue. So the queue maintains node collections whose fan-in = 0. The algorithm stops when there is no node in the queue.

2) How about the loop

We compare the number of nodes we visited (BFS) and the total number of nodes. If they are equal, there is no loop. Otherwise, there is a loop.

3) Key points

Queue: stores nodes with fan-in=0
HashMap: stores all nodes' fan-in number
BFS

4) Basic Algorithms

-----------------------------------------------------------
public int[] topologicalSort(int[][] edges, int n) throws Exception{
    Map<Integer, List<Integer>> graph = new HashMap<>();

    Queue<Integer> fanin0 = new LinkedList<>();
    Map<Integer, Integer> status = new HashMap<>();
 
    init(edges, n, graph, fanin0, status);

    List<Integer> result = new ArrayList<>();

    while(!queue.isEmpty()){
        int len = queue.size();

        //for all nodes whose fanin=0
        for(int i=0;i<len;i++){    
            int node = queue.poll();
            result.add(node);
         
            //for each child, update its fanin number, and if it is 0, add to queue fanin0
            for(int child:graph.get(node)){
                int fanin = status.get(child)-1;
                if(fanin==0) fanin0.add(child);
                status.put(child, fanin);
            }
        }
    }

    if(result.size()!=n) throw new Exception("there is a loop!");
    return toArray(result);
}

private void init(...){ ... }
private int[] toArray(...) { ... }
-----------------------------------------------------------

Compare topological sorting based on BFS and DFS

The BFS method has one advantage, compared to DFS. It can sort nodes without path order constraints, according to other ordering rules. (It is difficult to understand this, let's see the following example)

Given a directed graph (all nodes are represented by int), output an ordered array of nodes.

The requirement is:
Constraint1: If there is a path (0->1) in the graph, the result array should put node 0 in front of 1.
Constraint2: For two nodes which do not have constraint 1, the smaller node should be in front of the larger node in the output array

The output should only be: [0,1,2,4,3]
We cannot output [0,2,1,4,3]

Solution:
in the bfs method
---------------------------------------------------
    while(!queue.isEmpty()){
        int len = queue.size();
        Collections.sort(queue);
        //for all nodes whose fanin=0
        for(int i=0;i<len;i++){
---------------------------------------------------
Add one line, sort the queue. So all nodes with fan-in = k are sorted.

Questions:
[332] Reconstruct Itinerary
[207] Course Schedule
[269] Alien Dictionary

Index Tree

Segment Tree

Tree's Pre-Order, In-Order and Post-Order Traverse Summary

To traverse a tree, there r three basic ways: preorder, inorder and postorder. All the three methods can be implemented in recursion or non-recursion. Here to simplify the problem, we assume that the tree is a binary tree.

Recursion Traversal

It is easy to recursively traverse a tree.

1.Preorder: root->left->right

public traverse(TreeNode root){

    visit(root);

    traverse(root.left);

    traverse(root.right);

}

2.Postorder: left->right->root

public traverse(TreeNode root){

    traverse(root.left);

    traverse(root.right);

    visit(root);

}

3.Inorder traverse: left->root->right

public traverse(TreeNode root){

    traverse(root.left);

    visit(root);

    traverse(root.right);

}

Non-recursion Traversal

When implementing traversal using the non-recursive method, we might need some extra space (stack) to store some tree nodes. Morris Inorder Traversal presents a method to traverse a binary tree using O(1) space and O(n) time.

1.Preorder: root->left->right

Considering stack is the first-in-last-out Container, we should push the right node into stack before the left node so that the left node can be popped and visited earlier. //pop root, push right, push left

public traverse(TreeNode root){

    if(root==null) return ;

    Stack<TreeNode> stack = new Stack<>();

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode node = stack.pop();   //visit the node

        if(node.right!=null) stack.push(node.right);

        if(node.left!=null) stack.push(node.left);

    }

}

2.Postorder: left->right->root

Postorder is similar the preorder, but "first pop the root, then push the left, then push the right". So the visiting is like "root, right, left". In the end, reverse the sequence, we can get "left, right, root".

public traverse(TreeNode root){

    if(root==null) return ;

    Stack<TreeNode> stack = new Stack<>();

    List<TreeNode> list = new ArrayList<>();

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode node = stack.pop();

        list.add(node);

        if(node.left!=null) stack.push(node.left);     

        if(node.right!=null) stack.push(node.right);  

    }

    for(int i = list.size()-1;i>=0;i--){

        visit(list.get(i));

    }

}

3.Inorder traverse: left->root->right

public traverse(TreeNode root){

    if(root==null) return ;

    Stack<TreeNode> stack = new Stack<>();

    List<TreeNode> list = new ArrayList<>();

    TreeNode cur = root;

    while(true){

        if(root.left!=null){

            stack.push(root);

            cur = cur.left;

        }else{

            if(stack.isEmpty()){

                break;

            }else{

                TreeNode parent = stack.pop(); //visit the node now

                cur = parent.right;

            }

        }

    }

}

Morris Inorder Traverse

public traverse(TreeNode root){

    if(root==null) return ;

    TreeNode cur = root;

    while(cur!=null){

        if(cur.left==null){    //visit the right node next;

             visit(cur);

             cur = cur.right;

        }else{

             TreeNode predecessor = cur.left;

             //find the Predecessor of the cur node.

             while(predecessor.right!=null && predecessor.right!=cur) predecessor = predecessor.right;

             if(predecessor.right==null){

                 //have not visited cur node's left tree, build the blue link in the graph

                 predecessor.right = cur;

                 cur = cur.left;

             }else{

                 //have visited cur node's left tree, remove the blue link in the graph

                 predecessor.right = null;

                 visit(cur);

                 cur = cur.right;

             }

        }

    }

}