1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Pair implements Comparable<Pair> {
    int first;
    int second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair o) {
        if (first < o.first) return -1;
        else if (first > o.first) return 1;
        else {
            if (second < o.second) return -1;
            else if (second > o.second) return 1;
            return 0;
        }
    }
}

static ArrayList<Pair>[] adj = new ArrayList[20001];
for (int i = 0; i < adj.length; ++i)
    adj[i] = new ArrayList<Pair>();

1

static int[][] AdjMat = new int[101][101];

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Tuple implements Comparable<Tuple>{
    int first;
    int second, third;
    public Tuple(int a, int b, int c){
        first = a;
        second = b;
        third = c;
    }

    @Override
    public int compareTo(Tuple o) {
        if(first < o.first) return -1;
        else if(first > o.first) return 1;
        else{
            if(second < o.second) return -1;
            else if(second > o.second) return 1;
            else{
                if(third < o.third) return -1;
                else if(third > o.third) return 1;
                else return 0;
            }
        }
    }
}

Stack<Tuple> EdgeList = new Stack<Tuple>(); // (weight, two vertices) of the edge

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

//TODO: fix it ASAP
int INF = 1_000_000_000
Arrays.fill(d, INF);

Queue<Integer> queue = new ArrayDeque<>();

d[s] = 0;
queue.add(s);

while(!queue.isEmpty()){
    int u = queue.poll();

    for(int p=0; p<adjList[u].size(); ++p){
        Pair v = adjList[u].get(p);
        if(d[v] == INF){
            d[v.first] = d[u] + 1;
            queue.add(v.first);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

//at main
BFSData[] bfsData = new BFSData[2];
bfsData[0] = new BFSData(totalWordCnt);
bfsData[1] = new BFSData(totalWordCnt);

bfsData[0].q.offer(beginWord);
bfsData[0].distance[idx.get(beginWord)] =0;

bfsData[1].q.offer(endWord);
bfsData[1].distance[idx.get(endWord)] =0;


while(bfsData[0].q.size() > 0 && bfsData[1].q.size() > 0){
    int mode = 0;
    if(bfsData[0].q.size() > bfsData[1].q.size())
        mode = 1;
    
    int join = bfs(bfsData[mode], bfsData[1-mode]);
    if(join != -1)  //we found a join.
        return bfsData[0].distance[join] + bfsData[1].distance[join]+1;
}

private int bfs(BFSData primary, BFSData secondary){
    Queue<String> next = new ArrayDeque<>();
    while(!primary.q.isEmpty()){
        String uWord = primary.q.poll();
        int u = idx.getOrDefault(uWord, -1);
        
        if(secondary.distance[u] != -1)
            return u;

        List<String> keys = generateTransKey(uWord);

        for(String key: keys){
            List<Integer> kl = lookup.get(key);
            if(kl == null) continue;
            for(Integer ki: kl){
                if(primary.distance[ki] == -1){
                    next.offer(wordList.get(ki));
                    primary.distance[ki] = primary.distance[u]+1;
                }
            }
        }
    }
    
    primary.q = next;
    
    return -1;
}

class BFSData{
    Queue<String> q;
    int[] distance;
    List<Integer>[] parent;
    public BFSData(int n){
        q = new ArrayDeque<>();
        distance = new int[n];
        Arrays.fill(distance, -1);
        parent = new List[n];
        Arrays.fill(parent, null);
    }
    
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//iterative version
public static void dfs(int s) {
    visited = new boolean[V];

    // depth-first search using an explicit stack
    Stack<Integer> stack = new Stack<Integer>();
    visited[s] = true;
    stack.push(s);
    while (!stack.isEmpty()) {
        int v = stack.peek();
        int w = -1;
        for(int i=0; i<adjcnt[v]; ++i) {
            if (!visited[adj[v][i]])
                w = adj[v][i]; break;
        }
        if(w != -1){
            visited[w] = true;
            stack.push(w);
        }
        else {
            stack.pop();
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int[] dfs_num = new int[V];
Arrays.fill(dfs_num, UNVISITED);
void dfs(int u) { // DFS for normal usage: as graph traversal algorithm
    dfs_num[u] = VISITED; // important: we mark this vertex as visited
    for (int j = 0; j < AdjList[u].size(); j++) { // default DS: AdjList
        ii v = AdjList[u].get(j); // v is a (neighbor, weight) pair
        if (dfs_num[v.first] == UNVISITED) // important check to avoid cycle
            dfs(v.first); // recursively visits unvisited neighbors of vertex u
    }
} // for simple graph traversal, we ignore the weight stored at v.second

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/*
You can get the number of scc and the corresponding root.
init with
Arrays.fill(dfs_num, UNVISITED);
Arrays.fill(dfs_low, 0);
Arrays.fill(visited, false);
dfsNumberCounter = numSCC = 0;
*/

Stack<Integer> S;
int dfsNumberCounter;
int[] dfs_low;
boolean[] visited;
int[] dfs_num;
List<List<Pair>> AdjList;
int numSCC;
final  int UNVISITED = -1;
void tarjanSCC(int u) {
    dfs_low[u] = dfs_num[u] = dfsNumberCounter++; // dfs_low[u] <= dfs_num[u]
    S.push(u); // stores u in a vector based on order of visitation
    visited[u] = true;
    for (int j = 0; j < (int)AdjList.get(u).size(); j++) {
        Pair v = AdjList.get(u).get(j);
        if (dfs_num[v.first] == UNVISITED)
            tarjanSCC(v.first);
        if (visited[v.first]) // condition for update
            dfs_low[u] = Math.min(dfs_low[u], dfs_low[v.first]); }
    if (dfs_low[u] == dfs_num[u]) { // if this is a root (start) of an SCC
        ++numSCC;
        //System.out.format("SCC %d:", numSCC); // this part is done after recursion
        while (true) {
            int v = S.pop(); visited[v] = false;
            //System.out.format(" %d", v);
            if (u == v) break; }
        //System.out.print("\n");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int dr[] = {1,1,0,-1,-1,-1, 0, 1}; // trick to explore an implicit 2D grid
int dc[] = {0,1,1, 1, 0,-1,-1,-1}; // S,SE,E,NE,N,NW,W,SW neighbors

int floodfill(char[][] grid, int r, int c, char c1, char c2) { // returns the size of CC
    int R=grid.length; int C=R > 0? grid[0].length: 0;
    if (r < 0 || r >= R || c < 0 || c >= C) return 0; // outside grid
    if (grid[r][c] != c1) return 0; // does not have color c1
    int ans = 1; // adds 1 to ans because vertex (r, c) has c1 as its color
    grid[r][c] = c2; // now recolors vertex (r, c) to c2 to avoid cycling!
    for (int d = 0; d < 8; d++)
        ans += floodfill(grid, r + dr[d], c + dc[d], c1, c2);
    return ans; // the code is neat due to dr[] and dc[]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

//require tuple
//require union find
public int kruskal(ArrayList<Tuple> EdgeList, ArrayList<Tuple> result){
    Collections.sort(EdgeList);

    int mst_cost = 0;

    UnionFind UF = new UnionFind(m);
    UF.init();

    for (int i = 0; i < n; i++) {
        Tuple front = EdgeList.get(i);
        if (!UF.isSameSet(front.second, front.third)) {
            mst_cost += front.first;
            result.add(front);
            UF.unionSet(front.second, front.third);
        }
    }

    return mst_cost;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

//this version with distance
Arrays.fill(dist, INF);
dist[s] = 0; // INF = 1Billion to avoid overflow

PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
pq.offer(new Pair(0, s));
while (!pq.isEmpty()) { // main loop
    Pair front = pq.poll();
    int d = front.first, u = front.second;
    if (d > dist[u]) continue; // this is a very important check
    for (int j = 0; j < adj[u].size(); j++) {
        Pair v = adj[u].get(j); // all outgoing edges from u
        if (dist[u] + v.second < dist[v.first]) {
            dist[v.first] = dist[u] + v.second; // relax operation
            pq.offer(new Pair(dist[v.first], v.first));
        }
    }
} // this variant can cause duplicate items in the priority queue

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//require pair
static int[] dist = new int[102];
static final int INF = 1000000000;

//the result is in dist array
public void dijkstra(int e){
    Arrays.fill(dist, INF);
    dist[e] = 0; // INF = 1Billion to avoid overflow

    PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
    pq.offer(new Pair(0, e));
    while (!pq.isEmpty()) { // main loop
        Pair front = pq.poll();
        int d = front.first, u = front.second;
        if (d > dist[u]) continue; // this is a very important check
        for (int j = 0; j < adj[u].size(); j++) {
            Pair v = adj[u].get(j); // all outgoing edges from u
            if (dist[u] + v.second < dist[v.first]) {
                dist[v.first] = dist[u] + v.second; // relax operation
                pq.offer(new Pair(dist[v.first], v.first));
            }
        }
    } // this variant can cause duplicate items in the priority queue
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

ArrayList<Pair>[] adj = new ArrayList[201]; 
final int INF = 1_000_000_000;
int[] dist = new int[201];

//place the source at 0
public bellman_ford(int S){
    Arrays.fill(dist, INF);
    dist[S] = 0;
    for (int i = 0; i < n - 1; i++) // relax all E edges V-1 times
        for (int u = 0; u < n; u++) // these two loops = O(E), overall O(VE)
            for (int j = 0; j < adj[u].size(); j++) {
                Pair v = adj[u].get(j); // record SP spanning here if needed
                dist[v.first] = Math.min(dist[v.first], dist[u] + v.second); // relax
            }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Can be used to 
* detected the negative cycle
* SCC => if Adj[i][j] and Adj[j][i] are not INF, they belongs to same SCC.
* Radius of the graph
* Minmax

```java
static final int INF = 1000000000;

public void flyodWarshall(){
    // inside int main()
    // precondition: AdjMat[i][j] contains the weight of edge (i, j)
    // or INF (1B) if there is no such edge
    // AdjMat is a 32-bit signed integer array
    for (int k = 0; k < V; k++) // remember that loop order is k->i->j
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                AdjMat[i][j] = Math.min(AdjMat[i][j], AdjMat[i][k] + AdjMat[k][j]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

static final int INF = 1000000000;

public void flyodWarshall(){
    // inside int main()
    // precondition: AdjMat[i][j] contains the weight of edge (i, j)
    // or INF (1B) if there is no such edge
    // AdjMat is a 32-bit signed integer array
    for (int k = 0; k < V; k++) // remember that loop order is k->i->j
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if((AdjMat[i][k] + AdjMat[k][j] < AdjMat[i][j]) {
                    AdjMat[i][j] = AdjMat[i][k] + AdjMat[k][j];
                    p[i][j] = p[k][j]
                }
}

void printPath(int i, int j) {
    if (i != j) printPath(i, p[i][j]);
    System.out.print(" " + j);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int dfsNumberCounter = 0;
List<List<Pair>> AdjList = new ArrayList<>();
var dfs_num = new int[V];
var dfs_low = new int[V];
var dfs_parent = new int[V];
var articulation_vertex = new boolean[V];

final static int UNVISITED = -1;

Arrays.fill(dfs_num, UNVISITED);
Arrays.fill(dfs_low, 0);
Arrays.fill(dfs_parent, 0);
Arrays.fill(articulation_vertex, false);

void articulationPointAndBridge(int u) {
    dfs_low[u] = dfs_num[u] = dfsNumberCounter++; // dfs_low[u] <= dfs_num[u]
    for (int j = 0; j < (int)AdjList.get(u).size(); j++) {
        Pair v = AdjList.get(u).get(j);
        if (dfs_num[v.first] == UNVISITED) { // a tree edge
            dfs_parent[v.first] = u;
            if (u == dfsRoot) rootChildren++; // special case if u is a root
            articulationPointAndBridge(v.first);
            if (dfs_low[v.first] >= dfs_num[u]) // for articulation point
                articulation_vertex[u] = true; // store this information first
            //if (dfs_low[v.first] > dfs_num[u]) // for bridge
            //    bridges.add(new Pair(Math.min(u, v.first), Math.max(u, v.first)));
            dfs_low[u] = Math.min(dfs_low[u], dfs_low[v.first]); // update dfs_low[u]
        }
        else if (v.first != dfs_parent[u]) // a back edge and not direct cycle
            dfs_low[u] = Math.min(dfs_low[u], dfs_num[v.first]); // update dfs_low[u]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int[][] res = new int[maxV][maxV];
int mf, f, s, t; // global variables
int[] p; // p stores the BFS spanning tree from s
void augment(int v, int minEdge) { // traverse BFS spanning tree from s->t
    if (v == s) { f = minEdge; return; } // record minEdge in a global var f
    else if (p[v] != -1) {
        augment(p[v], Math.min(minEdge, res[p[v]][v]));
        res[p[v]][v] -= f; res[v][p[v]] += f;
    }
}

BitSet vis;

int fulkerson(int sIdx, int tIdx) {
    s = sIdx;
    t = tIdx;
    // inside int main(), assume that we have both res (AdjMatrix) and AdjList
    mf = 0;
    while (true) { // now a true O(VE^2) Edmonds Karp’s algorithm
        f = 0;
        BitSet vis = new BitSet(maxV); vis.set(s); // we change vi dist to bitset!
        p = new int[maxV]; Arrays.fill(p, -1);
        dfs(s);
        
        Queue<Integer> q = new ArrayDeque<>(); q.offer(s);
        
        augment(t, INF);
        if (f == 0) break;
        mf += f;
    }
    
    return mf;
}

dfs(int u){
    for (int j = 0; j < AdjList.get(u).size(); j++) { // AdjList here!
        int v = AdjList.get(u).get(j); // we use vector<vi> AdjList
        if (res[u][v] > 0 && !vis.get(v)) {
            vis.set(v);
            p[v] = u;
            dfs(v);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int[][] res = new int[maxV][maxV];
int mf, f, s, t; // global variables
int[] p; // p stores the BFS spanning tree from s
void augment(int v, int minEdge) { // traverse BFS spanning tree from s->t
    if (v == s) { f = minEdge; return; } // record minEdge in a global var f
    else if (p[v] != -1) {
        augment(p[v], Math.min(minEdge, res[p[v]][v]));
        res[p[v]][v] -= f; res[v][p[v]] += f;
    }
}

int edmondKarp(int sIdx, int tIdx) {
    s = sIdx;
    t = tIdx;
    // inside int main(), assume that we have both res (AdjMatrix) and AdjList
    mf = 0;
    while (true) { // now a true O(VE^2) Edmonds Karp’s algorithm
        f = 0;
        BitSet vis = new BitSet(maxV); vis.set(s); // we change vi dist to bitset!
        Queue<Integer> q = new ArrayDeque<>(); q.offer(s);
        p = new int[maxV]; Arrays.fill(p, -1);
        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == t) break;
            for (int j = 0; j < AdjList.get(u).size(); j++) { // AdjList here!
                int v = AdjList.get(u).get(j); // we use vector<vi> AdjList
                if (res[u][v] > 0 && !vis.get(v)) {
                    vis.set(v);
                    q.offer(v);
                    p[v] = u;
                }
            }
        }
        augment(t, INF);
        if (f == 0) break;
        mf += f;
    }
    
    return mf;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

//new code at: https://github.com/stevenhalim/cpbook-code/blob/master/ch8/maxflow.java

int[] d;
int dinic(int sIdx, int tIdx) {
    s = sIdx;
    t = tIdx;
    // inside int main(), assume that we have both res (AdjMatrix) and AdjList
    mf = 0;
    while (true) { // now a true O(VE^2) Edmonds Karp’s algorithm
        f = 0;
        vis = new BitSet(maxV); vis.set(s); // we change vi dist to bitset!
        Queue<Integer> q = new ArrayDeque<>(); q.offer(s);
        d = new int[maxV]; d[s] = 0;
        p = new int[maxV]; Arrays.fill(p, -1);
        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == t) break;
            for (int j = 0; j < AdjList.get(u).size(); j++) { // AdjList here!
                int v = AdjList.get(u).get(j); // we use vector<vi> AdjList
                if (res[u][v] > 0 && !vis.get(v)) {
                    vis.set(v);
                    q.offer(v);
                    d[v] = d[u] + 1;
                    p[v] = u;
                }
            }
        }

        int sf = 0;
        while(true){
            f = 0;
            augment(t, INF);
            if (f == 0) break;
            sf += f;

            vis = new BitSet(maxV); vis.set(s);
            p = new int[maxV]; Arrays.fill(p, -1);
            dfs2(s);
        }

        /*
        this is an optimization.
        for(int v=0; v<maxV; ++v){
            if(d[v]+1 == d[t]) {
                f = 0;
                augment(v, Math.min(INF, res[v][t]));
                res[v][t] -= f; res[t][v] += f;

                sf += f;
            }
        }
        */

        if(sf == 0) break;
        mf += sf;
    }
    
    return mf;
}

void dfs2(int u){
    for (int j = 0; j < AdjList.get(u).size(); j++) { // AdjList here!
        int v = AdjList.get(u).get(j); // we use vector<vi> AdjList
        if (d[v] == d[u]+1 && res[u][v] > 0 && !vis.get(v)) {
            vis.set(v);
            p[v] = u;
            dfs(v);
        }
    }
}

1

//TODO: to be completed

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int INF = 1_000_000_000
Arrays.fill(color, INF);

Queue<Integer> queue = new ArrayDeque<>();
bool isBipartite = true; 
color[s] = 0;
queue.add(s);

while(!queue.isEmpty() & isBipartite){
    int u = queue.poll();

    for(int p=0; p<adjList[u].size(); ++p){
        Pair v = adjList[u].get(p);
        if(visited[v] == INF){
            color[v.first] = 1 - color[u];
            queue.add(v.first);
        }
        else if(color[v.first] == color[u]){
            isBipartite = false;
            break;
        }
    }
}

1

//TODO: to be implemented

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int EXPLORED = 1;
int VISITED = 2;
int UNVISITED = 0;

ts = new ArrayList<Integer>();
for(int i=0; i<numCourses; ++i){
    //do dfs if not visted
    if(visited[i] == UNVISITED){
        boolean hasCycle = dfs(i);
        if(hasCycle) 
            System.out.println("Have cycle, no topological sort");
    }
}
Collections.reverse(ts);
ArrayList<Integer> result =ts;

boolean dfs(int u){
    visited[u] = EXPLORED;
    
    for(int i=0; i<adjList[u].size(); ++i){
        int v = adjList[u].get(i);
        //System.out.println("" + u + "->" + v + ":" + visited[v]);
        if(visited[v] == EXPLORED) return true;
        if(visited[v] == VISITED) continue;
        boolean hasCycle = dfs(v);
        if(hasCycle) return true;
    }
    order.add(u);
    
    visited[u] = VISITED;
    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

ArrayList<Integer> Kahn(int V) {
    //this either sort all, or fail to sort any.
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    ArrayList<Integer> answer = new ArrayList<Integer>();

    for(int i=0; i<V; ++i)
        if(indegree[i] == 0){
            queue.offer(i);
            indegree[i]--;
        }
    while(!queue.isEmpty()){
        int u= queue.poll();

        for(int j=0; j<adjcnt[u]; ++j){
            indegree[adj[u][j]]--;
        }

        for(int i=0; i<adjcnt[u]; ++i){
            int v = adj[u][i];
            if(indegree[v] == 0) {
                queue.offer(v);
                indegree[v]--;
            }
        }
        answer.add(u);
    }
    return answer;
}

1

//TOOD: to be completed

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//required numberOfSetBits
//set 1 to node which need to be matched
//second path contained the weight of the edge
private int weightedMCM(int bitmask){
    //pair up someone still not in a group and then return
    if(dp[bitmask] != INF) return dp[bitmask];
    if(NumberOfSetBits(bitmask) == N) return 0;

    int result = INF;
    for (int i = 0; i < N; i++) {
        if((bitmask & (1 << i)) != 0) continue;
        for (Pair p: adjList[i]) {
            if(i==p.first) continue;
            if((bitmask & (1 << p.first)) != 0) continue;
            int temp = dpHelper(bitmask | (1 << i) | (1 << p.first)) + p.second;
            if(temp < result)
                result = temp;
        }
    }

    dp[bitmask] =result;
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

class BST{
    TreeNode root;

    public RankFromStream(){
        root = null;
    }

    void add(int x){
        root = addHelper(root, val);
    }

    TreeNode addHelper(TreeNode root, int val){
        if(root == null)
            return new TreeNode(val);
        
        if(root.val == val){
            //no duplicate?
        }
        else if(root.val > val){
            root.left = addHelper(root.left, val);
        }
        else{
            root.right = addHelper(root.right, val);
        }

        return root;
    }

    void deleteKey(int key) { root = deleteRec(root, key); }
 
    /* A recursive function to
      delete an existing key in BST
     */
    TreeNode deleteRec(TreeNode root, int key)
    {
        /* Base Case: If the tree is empty */
        if (root == null)
            return root;
 
        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
 
        // if key is same as root's
        // key, then This is the
        // node to be deleted
        else {
            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
 
            // node with two children: Get the inorder
            // successor (smallest in the right subtree)
            root.key = minValue(root.right);
 
            // Delete the inorder successor
            root.right = deleteRec(root.right, root.key);
        }
 
        return root;
    }
 
    int minValue(TreeNode root)
    {
        int minv = root.key;
        while (root.left != null)
        {
            minv = root.left.key;
            root = root.left;
        }
        return minv;
    }
}

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    //int leftSize;  for checking rank

    public RankTreeNode(int val){
        this.val = val;
        //this.leftSize = 0;
    }
}

1
2
3
4
5
6

private void postOrder(TreeNode node) { 
    if (node == null) { return; } 
    postOrder(node.left); 
    postOrder(node.right); 
    System.out.printf("%s ", node.data); 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

ArrayList<Integer> postOrderIterative(Node node) {
    Stack<Node> S = new Stack<Node>();
    ArrayList<Integer> list = new ArrayList<>();
        
    // Check for empty tree
    if (node == null)
        return list;
    S.push(node);
    Node prev = null;
    while (!S.isEmpty())
    {
        Node current = S.peek();

        /* go down the tree in search of a leaf an if so process it
        and pop stack otherwise move down */
        if (prev == null || prev.left == current ||
                                    prev.right == current) {
            if (current.left != null)
                S.push(current.left);
            else if (current.right != null)
                S.push(current.right);
            else {
                S.pop();
                list.add(current.data);
            }

            /* go up the tree from left node, if the child is right
            push it onto stack otherwise process parent and pop
            stack */
        } else if (current.left == prev) {
            if (current.right != null)
                S.push(current.right);
            else {
                S.pop();
                list.add(current.data);
            }
                
            /* go up the tree from right node and after coming back
            from right node process parent and pop stack */
        } else if (current.right == prev) {
            S.pop();
            list.add(current.data);
        }
        prev = current;
    }

    return list;
}

1
2
3
4
5
6

private void inorder(TreeNode node) { 
    if (node == null) { return; } 
    postOrder(node.left); 
    System.out.printf("%s ", node.data); 
    postOrder(node.right); 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

ArrayList<Integer> void inorder(){
    ArrayList<Integer> list = new ArrayList<>();
    if (root == null)
        return list;

    Stack<Node> s = new Stack<Node>();
    Node curr = root;

    // traverse the tree
    while (curr != null || s.size() > 0) {

        /* Reach the left most Node of the
        curr Node */
        while (curr !=  null) {
            /* place pointer to a tree node on
                the stack before traversing
                the node's left subtree */
            s.push(curr);
            curr = curr.left;
        }

        /* Current must be NULL at this point */
        curr = s.pop();

        list.add(curr.data);

        /* we have visited the node and its
            left subtree.  Now, it's right
            subtree's turn */
        curr = curr.right;
    }
}