

Interview preparation kit, Tree

LCA

• Please refer here for LCA.

Is this a BST?

• Thought: Given the property of BST, where root's value > max of left subtree but < min of right shubtree. So we descend down the whole tree and check the property recursively. For more information, please check the comment part of the code.
• Analysis:
  • Time complexity: O(N), where N is the nodes of given tree.
  • Spacee complexity: O(N), where N is the nodes of given tree. or O(1) if the tree itself does not taken into account.

    bool checkBST(Node* root) 
    {
        if(root == NULL)
        {
           return true; 
        }
    
        int lsub_max = 0, rsub_min = INT_MAX;
        sub_treemax(root -> left, lsub_max);
        sub_treemin(root -> right, rsub_min);
    
        if(root -> data <= lsub_max) // violates the property
        {
            return false;
        }
    
        if(root -> data >= rsub_min) // violates the property
        {
            return false;
        }
    
        return checkBST(root -> left) && checkBST(root -> right) ; // descend and recursively checking the whole tree
    
    }
    
    void sub_treemax(Node* root, int& sub_max)
    {
        if(root == NULL)
        {
            return;
        }
    
        sub_max = max(root -> data, sub_max);
        sub_treemax(root -> left, sub_max);
        sub_treemax(root -> right, sub_max);
    }
    
    void sub_treemin(Node* root, int& sub_min)
    {
        if(root == NULL)
        {
            return;
        }
    
        sub_min = min(root -> data, sub_min);
        // printf("data %d, submin update to %d\n", root -> data, sub_min);
        sub_treemin(root -> left, sub_min);
        sub_treemin(root -> right, sub_min);
    }
    

Height of Binary Tree

• Thought: Dig, traverse until the leaf node and update the height
• Analysis:
  • Time complexity: O(N), where N is the nodes of given tree.
  • Spacee complexity: O(N), where N is the nodes of given tree. or O(1) if the tree itself does not taken into account.

    int height(Node* root) 
    {
        return dfs(root, 0);
    }
    int dfs(Node* root, int cur_depth)
    {
        return root == NULL ? cur_depth - 1 : max(dfs(root -> left, cur_depth + 1), dfs(root -> right, cur_depth + 1));
    }

Huffman Decoding

• Thought:

  • Step 1. Iterate throught the encoded string
  • Step 2. Move according to the encoded string and update the position of iteration
  • Step 3. Return the result once reach the leaf node and concatenate the new character

• Analysis, assume the alphabet in the leaf are N (i.e. N symbols are constructed to form the huffman tree):

  • Time complexity: O(NlogN), since we decode O(N) symbols at most, and each symbols takes O(logN) time to decode (descend the tree), thus total time complexity being O(NlogN).

    char descend_tree(node* root, string decoded, const string& encoded, int& encoded_pos)
    {
        if(root -> left == NULL && root ->right == NULL) // Step 3.
        {
            return root -> data;
        }
        if(encoded[encoded_pos] == '0') // goes left (Step 2.)
        {
            encoded_pos++;
            return descend_tree(root -> left, decoded, encoded, encoded_pos);
        }
        else // goes right (Step 2.)
        {
            encoded_pos++;
            return descend_tree(root -> right, decoded, encoded, encoded_pos);
        }
    }
    
    void decode_huff(node * root, string s) 
    {
        int n = s.size();
        string final_res(""); 
        for (int i = 0; i < n;) // Step 1.
        {
            final_res += descend_tree(root, "", s, i);
        }
        cout << final_res << '\n';
    }