算法积累一(树和图部分) Algorithms - Tree and Graph

Binary Search Tree:

What’s is BST?

BST is binary tree which left child is smaller than parent, right child is bigger than parent.
How to find the minimum value?

Because BST left child is smaller than parent, so find left child until it is NULL.
How to output ascending order for a BST?

Inorder traversal. Left->parent->right, then the output is sorted

Inorder successor?

First, the inorder successor, is just the element which follows the node in ascending order.

If already has ascending order, then find the next element is OK, otherwise

Method 1

If node’s right child is not NULL, then find the min value of right subtree, which is the inorder successor. Reason: right subtree are all bigger than the node, only find the min of right subtree is fine.
If node’s right child is NULL. Then its inorder successor must be its ancestor. If the treenode structure contains parent pointer, then it goes up to find one node A which A is A’s parent’s left child. Then A’s parent is inorder successor. Why? Reason: inorder successor is the node which is bigger than the node but the minimum one. For example, want to get node N’s inorder successor. If N is a left child, then its parent is its successor. It satisfies the requirement. N is parent’s left child, so N’s parent is succ. If N is a right child, N’s parent M is N’s grandparent’s left child, then M’s parent is succ.

The above method requirement each treenode keeps parent pointer. There is another method which search from root, no need for parent pointer.

Method 2

If node’s right child is not NULL, then find the min value of right subtree, which is the inorder successor. Reason: right subtree are all bigger than the node, only find the min of right subtree is fine.
Travel down the tree, if the node’s value is greater than root’s value, then go right side, otherwise go left.

Both method’s time complexity is O(h), h is the height of tree.

class TreeNode{
    TreeNode* left;
  	TreeNode* right;
  	TreeNode* parent;
  	int value;
  	TreeNode(int v): left(nullptr), right(nullptr), parent(nullptr), value(v) {};
}
TreeNode* minValue(TreeNode* root){
    TreeNode* cur = root;
  	while(cur->left != nullptr){
        cur = cur->left;
    }
  	return cur;
}
// Method 1: make use of parent to find its successor
TreeNode* inOrderSuccessor(TreeNode* node){
    if(node->right != nullptr){
		return minValue(node);
    }
  	else{
        TreeNode *p = node->parent;
      	while(p!=nullptr && node == p->right){
            node = p;
          	p = p->parent;
        }
      	return p;
    }
}
// Method 2: search from root
TreeNode* inOrderSuccessor2(TreeNode* node, TreeNode* root){
    if(node->right != nullptr){
        return minValue(node);
    }
  	else{
        TreeNode *succ = nullptr;
      	while(root != nullptr){
          	// node is at left part, then the root could be its successor
            if(node->value < root->value){ // node is at left part
 				succ = root;
              	root = root->left;
            }
          	else if(node->value > root->value){ // node is at right part
          		root = root->right; // go right side to find bigger one      
            }
          	else{
                break;
            }
        }
      	return succ;
    }
}

Topological Sorting

If the set exists partial order(偏序) relation, then it exists topological sort. If the order is total order(全序), then the topological sort is unique. In graph, the partial order is called DAG(Directed Acyclic Graph有向无环图)。

There are two methods to achieve topological sorting, one is Kahn algorithm, another one is DFS.

Method 1 Kahn(Time Complexity is O(V+E))

Store all vertices that in-degree is 0 in queue Q.
select one node from Q, then delete all edges from this node, modify others degree. Add new nodes with 0 in-degree into Q.
If finally, there still some node not be vistited, then this graph is not DAG, means it has cycle.

Method 2 DFS(Time Complexity is O(V+E))

Starts with one vertex then visited its adjacetory vertices, store the results into stack, then output from stack.(store sequence is reverse to the topological sort).

// Method 1 Kahn, in-degree
// Before it has V for vertices, E for edges, adj for adjacetory edges, G for graph
void topologicalSort(){
    vector<int> inDegree(V, 0);
  	
  	// Time Complexity is O(V+E)
  	// Outer V, inner E
  	for(int i=0; i<V; i++){
        list<int>::iterator iter;
      	for(iter = adj[i].begin(); iter != adj[i].end(); iter++){
            inDegree[*iter]++;
        }
    }
  
  	queue<int> Q; // Store 0 indegree nodes
  	for(int i=0; i<V; i++){
        if(inDegree[i] == 0)
          Q.push(i);
    }
  
  	int cnt = 0; // To check cycle
  	vector<int> topoOrder;
  	while(!Q.empty()){
        int node = Q.front();
      	Q.pop();
      	topoOrder.push_back(node);
      	cnt++;
      	// Modify adj vertices' degree
      	for(auto iter = adj[node].begin(); iter != adj[node].end(); iter++){
            if(--inDegree[*iter] == 0){
                Q.push(*iter);
            }
        }
    }
  
  	if(cnt != V){
        cout << "Non-DAG" << endl;
      	return;
    }
  	// output topoOrder
}

// Method 2 DFS
void topologicalSortUtil2(int v, vector<bool> visited, stack<int>& Stack){
    visited[v] = true; // Mark visited
  	for(auto iter = adj[v].begin(); iter != adj[v].end(); iter++){
      	if(!visited[*iter])
	        topologicalSortUtil(*iter, visited, Stack);
    }
  	Stack.push(v);
}
void topologicalSort2(){
    stack<int> Stack;
  	vector<int> visited(V, false);
  	for(int i=0; i<V; i++){
        if(!visited[i]){
            topologicalSortUtil2(i, visited, Stack);
        }
    }
  	while(!Stack.empty()){ // reverse output
        cout << Stack.top() << endl;
      	Stack.pop();
    }
}
// Improvement for DFS, previous one cannot detect cycle.
// Use three different markers
void topologicalSortUtil3(int v, vector<int> visited, deque<int>& Deque){
  	// 0 for not visited, 1 for temporatory visited, 2 for permanent visited
    if(visited[v] == 1){
      	cout << "Non DAG" << endl;
        exit(0);
    }
  	if(visited[v] == 2){
        return;
    }
  	visited[v] = 1;
  	for(int i=0; i<V; i++){ // Here not check visited
        topologicalSortUtil3(i, visited, Deque);
    }
  	
  	visited[v] = 2;
  	Deque.push_front(v);
}
void topologicalSort3(){
    deque<int> Deque;
  	vector<int> visited(V, 0);
  	for(int i=0; i<V; i++){
        if(visited[v] == 0){
            topologicalSortUtil3(i, visited, Deque);
        }
    }
  	// Output deque
}


1. **Tree Traversal**:
   1. some common tree traversal algorithms: DFS, BFS, Pre-order, In-order, Post-order, Level traversal. Actually, Pre, In and Post belong to DFS, and Level belongs to BFS.
   2. ```c++
      class TreeNode(){
      public:
          int value_;
          TreeNode *left_;
          TreeNode *right_;
          TreeNode(int val){
              value_ = val;
              left_ = nullptr;
              right_ = nullptr;
          }
      };
      // BFS
      vector<int> BFS(TreeNode *root){
          queue<TreeNode*> q_nodes;
          vector<int> result;
          q_nodes.push(root);
          while(!q_nodes.empty()){
              TreeNode *top = q_nodes.top();
              q_nodes.pop();
              result.push_back(top->value_);
              if(top->left_){
                  q_nodes.push(top->left_);
              }
              if(top->right_){
                  q_nodes.push(top->right_);
              }
          }
          return result;
      }
      // DFS
      void DFSUtil(TreeNode *node, vector<int>& res){
          if(!node) return;
          res.push_back(node->value_);
          DFSUtil(node->left_, res);
          DFSUtil(node->right_, res);
      }
      vector<int> DFS(TreeNode *root){
          vector<int> result;
          DFSUtil(root, result);
          return result;
      }
      // Iteration for DFS
      vector<int> DFS(TreeNode *root){
          stack<TreeNode*> s_nodes;
          vector<int> result;
          s_nodes.push(root);
          while(!s_nodes.empty()){
              TreeNode *top = s_nodes.top();
              s_nodes.pop();
              result.push_back(top->value_);
              if(top->right_){
                  s_nodes.push_back(top->right_);
              }
              if(top->left_){
                  s_nodes.push_back(top->left_);
              }
          }
          return result;
      }
      // PreOrder, InOrder, PostOrder
      void PreOrderUtil(TreeNode *root, vector<int>& res){
          if(!root) return;
          res.push_back(root->value_);
          PreOrderUtil(root->left_, res);
          PreOrderUtil(root->right_, res);
      }
      vector<int> PreOrder(TreeNode *root){
          vector<int> res;
          PreOrderUtil(root, res);
          return res;
      }
      void InOrderUtil(TreeNode *root, vector<int>& res){
          if(!root) return;
          InOrderUtil(root->left_, res);
          res.push_back(root->value_);
          InOrderUtil(root->right_, res);
      }
      vector<int> InOrder(TreeNode *root){
          vector<int> res;
          InOrderUtil(root, res);
          return res;
      }
      void PostOrderUtil(TreeNode *root, vector<int>& res){
          if(!root) return;
          PostOrderUtil(root->left_, res);
          PostOrderUtil(root->right_, res);
          res.push_back(root->value_);
      }
      vector<int> PostOrder(TreeNode *root){
          vector<int> res;
          PostOrderUtil(root, res);
          return res;
      }

Level Traversal

Use vector to store all nodes, and cur and last to show each level

void level_tree(node* root){
    vector<node*> v;
  	int cur=0;
  	int last = 1;
  	v.push_back(root);
  	while(cur < v.size()){
        last = v.size();
      	while(cur < last){ // This is one level
            cout << v[cur]->val << ' ';
          	if(v[cur]->left){
                v.push_back(v[cur]->left);
            }
          	if(v[cur]->right){
                v.push_back(v[cur]->right);
            }
          	cur++;
        }
      	cout << endl; // 一层换行
    }
}

BFS, queue to only store one level’s nodes

void level_tree(node* root){
    queue<node*> q;
  	q.push(root);
  	while(!q.empty()){
      	int s = q.size();
      	while(s){
            auto n = q.top();
            q.pop();
            cout << n->val << " ";
            if(n->left){
                q.push(n->left);
            }
          	if(n->right){
                q.push(n->right);
            }
          	s--;
        }
      	cout << endl; //一层换行
    }
}

Trie:

Also called prefix tree, one simple implementation is use 26 fixed number as its tree node element.

// Implementation for Trie
class TreeNode{
public:
    vector<TreeNode*> children_;
    bool is_leaf_;
    TreeNode(){
        children_ = vector<TreeNode*> (26, nullptr);
        is_leaf_ = false;
    }
};
class Trie{
public:
    Trie();
    void insert(string word);
    bool search(string word);
    bool StartsWith(string prefix);
    ~Trie();
private:
    TreeNode *root;
};
void Trie::insert(string word){
    TreeNode *node = root;
    int index = 0;
    for(auto& ch : word){
        index = ch - 'a';
        if(!node->children_[index]){
            node->children_[index] = new TreeNode();
        }
        node = node->children_[index];
    }
    node->is_leaf_ = true;
}
bool Trie::search(string word){
    TreeNode *node = root;
    for(auto& ch : word){
        int index = ch - 'a';
        if(!node->children_[index]) return false;
        node = node->children_[index];
    }
    if(node->is_leaf_) return true;
    return false;
}
bool Trie::StartsWith(string prefix){
    TreeNode *node = root;
    for(auto& ch : prefix){
        int index = ch - 'a';
        if(!node->children_[index]) return false;
        node = node->children_[index];
    }
    return true;
}
Trie::Trie(){
    root = new TreeNode();
}
Trie::~Trie(){
    delete root;
}

Single Source Shortest Path

Bellman-Ford and Dijkstra: B can solve this problem with neg weight, but not neg cycle. D fits only for pos.
If all weight is equal, then Dijkstra equals to DFS

Implementation of Dijkstra with adj matrix and adj list

adj matrix, time complexity: O(V^2)

const int V = 9; // number of vectices
int MinDistance(vector<int>& dist, vector<bool>& is_shortest_path){
    int min_dist = INT_MAX, min_index;
  	for(int v=0; v < V; v++){
        if(is_shortest_path[v] == false && dist[v] <= min_dist){
            min_dist = dist[v], min_index = v;
        }
    }
  	return min_index;
}
void Dijkstra(vector<vector<int> >& graph, int src){
    vector<int> dist(V, INT_MAX);
  	vector<bool> is_shortest_path(V, false);
  
  	dist[src] = 0;
  
  	for(int cnt = 0; cnt < V - 1; cnt++){
      	// Pick the min dist vertex, src will be the first one
        int min_index = MinDistance(dist, is_shortest_path);
      	is_shortest_path[min_index] = true;
      	// Find all its neighbors and update them
      	for(int v = 0; v < V; v++){
            if(!is_shortest_path[v] && graph[min_index][v]
              && dist[min_index] != INT_MAX
              && dist[min_index] + graph[min_index][v]
              < dist[v]){
                dist[v] = dist[min_index] + graph[min_index][v];
            }
        }
    }
  	// Output result for dist
}

This code only calculates shortest distance, but not path information. If want, could cfreate a parent vector to store the info.

If only interested in signle source to target, then we can prune the search tree by break.

If use adj list, the time complexity could reduce to O(ElogV)

adj list, time complexity: O(ElogV)

// Dijkstra for adj list
// Will use priority queue to store the distance between vertices
// STL default priority queue is max queue, therefore need to modify
class Node{
    int index_;
  	int weight_;
  	Node(): index_(0), weight_(0){};
  	Node(int index, int weight): index_(index), weight_(weight){};
};
class Graph{
    int V_;
  	vector<list<Node> > adj_list_;
  	Graph(V){
        V_ = V;
      	adj_list_ = vector(V, list<Node>);
    }
};
class CompDist{
public:
	bool operator()(const pair<int,int>& lhs, const pair<int,int>& rhs) const{
        return lhs.second > rhs.second;
    }
};
void Dijkstra(Graph& graph, int src){
    int V = graph.V_;
  	// dist stores dist from src to all other vertices
  	vector<int> dist(V, INT_MAX);
  	// priority queue store the same with dist, the reason for using two containers is that: vector is fit for index, priority queue is fit for fetch dist
  	priority_queue<pair<int,int>, vector<pair<int,int> >, CompDist> dist_heap;
  
  	// The function of visited is: A->B is 3, C->B is 5, but C->B is updated beforehead, so heap now contains B, then A->B updates B again, there are two Bs in heap. Then the smaller B will be popped up, the bigger one will never be visited.
  	vector<bool> visited(V, false);
  	dist[src] = 0;
  	dist_heap.push(make_pair(src, 0));
  	while(!dist_heap.empty()){
        auto top_node = dist_heap.top();
      	int min_index = top_node.first;
      	int min_weight = top_node.second;
      	dist_heap.pop();
      	if(visited[min_index]){
            continue;
        }
      	visited[min_index] = true;
      	for(auto iter = graph[min_index].begin(); iter != graph[min_index].end(); iter++){
            if(dist[*iter.index_] > dist[min_index] + min_weight){
                dist[*iter.index_] = dist[min_index] + min_weight;
              	dist_heap.push(make_pair(*iter.index_, dist[*iter.index_]));
            }
        }
    }
  	// Output dist
}

Time complexity Analysis: For myself, I first analyze the time complexity is VElogV, which is different from the correct answer ElogV? Why? The reason is: inner loop times should be N(single vertex’s edges, not all edges), so the time complexity is VNlogV, VN == E, so the time complexity is ElogV.

Any two points shortest path

Methods: Run Dijkstra in each point; Use Floyd-Warshall algorithm.

Floyd is dp problem. Time complexity is O(V^3)

// Graph is adj matrix and INT_MAX for not available 
void FloydWarshall(vector<vector<int> >& graph, int V){
    for(int k=0; k<V; k++){
        for(int i=0; i<V; i++){
            for(int j=0; j<V; j++){
				if(graph[i][j] > graph[i][k] + graph[k][j]){
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

Some common problems

Determine if a binary tree is a balanced tree

int Level(TreeNode *node){
    if(!node) return 0;
  	else
      return max(Level(node->left), Level(node->right)) + 1;
}
bool IsBalancedTree(TreeNode *root){
    if(root == nullptr) return true;
  	else if(abs(Level(root->left) - Level(root->right)) <= 1
           && IsBalancedTree(root->left) && IsBalancedTree(root->right)){
        return true;
    }
  	return false;
}

This recursive method is too slow. So can use memory to store the value to improve the speed

// Define inbalance as -1
const int kInBalance = -1;
int IsBalancedUtil(TreeNode *node){
    if(!node) return 0;
  	int left_height = IsBalancedUtil(node->left);
  	if(left_height == kInBalance){
        return kInBalance;
    }
  	int right_height = IsBalancedUtil(node->right);
  	if(right_height == kInBalance){
        return kInBalance;
    }
  	if(abs(left_height - right_height) > 1){
        return kInBalance;
    }
  	return max(left_height, right_height) + 1;
}
bool IsBalancedTree(TreeNode *root){
    if(IsBalancedUtil(root) == kInBalance) return false;
  	return true;
}

Time complexity is O(n)

Check if a binary tree is a BST. No elements have the same value

There is very straight method is InOrder traversal then check if ascent. Not optimal, the definition of BST is left < parent < right. Left subtree < parent < Right subtree.

bool IsBSTUtil(TreeNode *node, int min, int max){
    if(!node) return true;
  	if((node->val < max || (node->val == max && node->right == nullptr)) && (node->val > min || (node->val == min && node->left == nullptr)) && (IsBSTUtil(node->left, min, node->val) && (IsBSTUtil(node->right), node->val, max))
       return true;
    return false;
                                                                                                                                               )
}
bool IsBST(TreeNode *root){
    return IsBSTUtil(root, INT_MIN, INT_MAX);
}

Time complexity O(n)

Tree 1 and Tree 2 are both binary trees nodes having values, determine if Tree 2 is a subtree of Tree 1

bool Match(TreeNode* node1, TreeNode* node2){
    if(node1 == nullptr && node2 == nullptr) return true;
  	if(node1 == nullptr || node2 == nullptr) return false;
  	if(node1->val != node2->val) return false;
  	return Match(node1->left, node2->left) && Match(node1->right, node2->right);
}
bool IsSubTree(TreeNode*root1, TreeNode* root2){
  	if(root2 == nullptr) return true;
  	if(root1 == nullptr) return false;
  	if(root1->val == root2->val){
        return Match(root1, root2);
    }
    else{
        return IsSubTree(root1->left, root2) || IsSubTree(root1->right, root2);
    }
}

Time Complexity O(MN)