This course covers the intuition, implementation and problem-solving using tries.

edited - Advanced Data Structures - TRIES (1).png

Trie is an efficient tree-like data structure used to store and retrieve information. It is frequently tested in coding interviews, indicating its widespread use in solving many real-world software engineering challenges.

This course covers every aspect of the trie data structure, from the intuition of building a trie to coding it in famous programming languages for solving algorithmic problems and designing real-world systems. It assumes a prior knowledge of trees and basic data structures like lists and arrays. 

The problems in this course are categorized into various patterns, which will help you map new solutions to known issues using tries. The problems are of varying difficulties, from easy to hard, thus giving you an iterative learning experience. By the end of this course, you’ll be able to decode relevant trie problems, code their solutions in C++ and Java, and apply trie concepts to design complex software systems.

Advanced Data Structures: Implementing Tries in C++ and Java

#include <iostream>
#include <vector>
using namespace std;

int maxSubarrayXOR(vector<int> nums) {
  // your code goes here
  return -1;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

// Definition of TrieNode
class TrieNode
{
    public:
       	// the integer value stored at the leaf node
        int value;
       	// each trie node can have only two children (0 and 1)
        TrieNode *children[2];
};

class Trie
{
    public:
        TrieNode * root;
        Trie()
        {
            root = new TrieNode();
        }
    
       	// Inserts a number into trie
        void insert(int num)
        {
            TrieNode *curr = root;
            for (int i = 31; i >= 0; i--)
            {
            	// Start from the MSB, insert all bits into Trie
                bool bit = num &(1 << i);	// Find current bit
                if (!curr->children[bit])	
                    // Create a new node if needed
                    curr->children[bit] = new TrieNode();
                    
                curr = curr->children[bit];
            }
    
            // Store value at leaf node
            curr->value = num;	
        }
    
       	// Finds the maximum XOR for input number in Trie
        int findMaxXOR(int num)
        {
            TrieNode *curr = root;
            for (int i = 31; i >= 0; i--)
            {
                // Find current bit in given prefix
                bool bit = num &(1 << i);	
    
               	// Traverse Trie, first look for a
               	// prefix that has opposite bit
                if (curr->children[!bit] != NULL)
                    curr = curr->children[!bit];
    
               	// If there is no prefix with opposite
               	// bit, then look for same bit.
                else if (curr->children[bit] != NULL)
                    curr = curr->children[bit];
            }
    
            return num ^ (curr->value);
        }
};

// Returns maximum XOR value of a subarray in arr[0..n-1]
int maxSubarrayXOR(vector<int> nums)
{
   	// Intialize a trie
    Trie *trie = new Trie();

    // Intialize a trie with zero
    trie->insert(0);	

   	// Initialize answer and xor of current prefix
    int result = INT_MIN, currXOR = 0;
    for (int i = 0; i < nums.size(); i++)
    {
    	// Traverse all input array element
        currXOR = currXOR ^ nums[i];
        
        // update current prefix xor and insert it into Trie
        trie->insert(currXOR);	

       	// Query for current prefix xor in Trie and update result if required
        result = max(result, trie->findMaxXOR(currXOR));
    }

    return result;
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
   public static int maxSubarrayXOR(List<Integer> nums) {
        // your code goes here
        return -1;
    }
}

import java.util.*;
import java.lang.*;
import java.io.*;

// Definition of TrieNode
class TrieNode
{
   	// the integer value stored at the leaf node
    int value;
   	// each trie node can have only two children (0 and 1)
    TrieNode children[] = new TrieNode[2];
}

class Trie
{
   	// Initialize a trie root
    TrieNode root = new TrieNode();

   	// function insert new number in trie
    void insert(int num)
    {
       	// initialize current node to root
        TrieNode curr = root;

       	// start from the most significant bit, insert all
       	// bit of integer into trie
        for (int i = 31; i >= 0; i--)
        {
           	// find current bit in given prefix
            int currentBit = ((num >> i) &1);

           	// Create a new node in the trie
            if (curr.children[currentBit] == null)
            {
                curr.children[currentBit] = new TrieNode();
            }

            curr = curr.children[currentBit];
        }

       	// store the integer value at the leaf node
        curr.value = num;
    }

    int findMaxXOR(int num)
    {
       	// initialize current node to root
        TrieNode curr = root;
        for (int i = 31; i >= 0; i--)
        {
           	// find current bit in given prefix
            int currentBit = ((num >> i) &1);

           	// check for prefix that has opposite bit
            if (curr.children[1 - currentBit] != null)
            {
                curr = curr.children[1 - currentBit];
            }

           	// check for same bit, if opposite bit not found
            else
            {
                curr = curr.children[currentBit];
            }
        }

       	// return xor value of maximum bit difference value
       	// so we get maximum xor value
        return curr.value ^ num;
    }
}

class Solution
{
   	// Returns maximum XOR value of pair in the given list of integers
    public static Integer maxSubarrayXOR(List<Integer> nums)
    {
       	// Intialize a trie
        Trie trie = new Trie();

        // Intialize trie with 0
        trie.insert(0);	

       	// Initialize answer and xor of current prefix
        int result = 0, currXOR = 0;
        for (int i = 0; i < nums.size(); i++)
        {
        	// Traverse all input array element
            currXOR = currXOR ^ nums.get(i);
            
            // update current prefix xor and insert it into Trie
            trie.insert(currXOR);	

           	// Query for current prefix xor in Trie and update result if required
            result = Integer.max(result, trie.findMaxXOR(currXOR));
        }

        return result;
    }
}

Java

#include<bits/stdc++.h>
using namespace std;

int maxSubarrayXOR(vector<int> nums) {
	// Initialize result
	int ans = INT_MIN;	 
	// Pick starting points of subarrays
	for (int i=0; i<nums.size(); i++) { 
		// to store xor of current subarray
		int currXOR = 0; 
		// Pick ending points of subarrays starting with i
		for (int j=i; j<nums.size(); j++) {
			currXOR = currXOR ^ nums[j];
			ans = max(ans, currXOR);
		}
	}
	return ans;
}

// Driver program to test maxSubarrayXOR function
int main() {
	vector<int> nums = {8, 1, 2, 12};
	cout << maxSubarrayXOR(nums);
	return 0;
}


import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static int maxSubArrayXOR(List<Integer> nums) {
		 // Initialize result
        int ans = Integer.MIN_VALUE;	
		// Pick starting points of subarrays
	    for (int i=0; i<nums.size(); i++) { 
			// to store xor of current subarray
		    int currXOR = 0; 
		    // Pick ending points of subarrays starting with i
		    for (int j=i; j<nums.size(); j++) {
			    currXOR = currXOR ^ nums.get(j);
			    ans = Integer.max(ans, currXOR);
		    }
	    }
	    return ans;
    }

    public static void main( String args[] ) {
        List<Integer> nums = Arrays.asList(8, 1, 2, 12);
        int maxXOR = maxSubArrayXOR(nums);
        System.out.println(maxXOR);
        
    }
}

Solve a hard-level problem for finding the maximum subarray XOR value in an array using tries.

Maximum Subarray XOR

Problem statement

Example 1

Example 2

Try it yourself

Intuition