Count Strings
Problem Statement :
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.
We define to be a valid regular expression if:
1) is "" or "".
2) is of the form "", where and are regular expressions.
3) is of the form "" where and are regular expressions.
4) is of the form "" where is a regular expression.
Regular expressions can be nested and will always have have two elements in the parentheses. ('' is an element, '' is not; basically, there will always be pairwise evaluation) Additionally, '' will always be the second element; '' is invalid.
The set of strings recognized by are as follows:
1) If is "", then the set of strings recognized .
2) If is "", then the set of strings recognized .
3) If is of the form "" then the set of strings recognized = all strings which can be obtained by a concatenation of strings and , where is recognized by and by .
4) If is of the form "" then the set of strings recognized = union of the set of strings recognized by and .
5) If is of the form "" then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by .
Task
Given a regular expression and an integer, , count how many strings of length are recognized by it.
Input Format
The first line contains the number of test cases . test cases follow.
Each test case contains a regular expression, , and an integer, .
Output Format
Print T lines, one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 10^9 + 7.
Solution :
Solution in C :
In C++ :
#include<stdio.h>
#include<vector>
#include<set>
#include<stdlib.h>
#include<map>
#include<string.h>
#include<iostream>
using namespace std ;
typedef pair<int,int> P ;
#define INF (int)1e9
#define MOD 1000000007
#define MAXN 102
int n,out[MAXN],g[MAXN][MAXN] ;
int ga[MAXN][MAXN],gb[MAXN][MAXN] ;
int g2[MAXN][MAXN] ;
set<int> aMask[MAXN],bMask[MAXN] ;
P construct(char regex[],int low,int high)
{
int start = n++ ;
int end = n++ ;
if(low == high)
{
out[start] = regex[low] - 'a' ;
return P(start,end) ;
}
int mid,ct = 0 ;
for(mid = low + 1;mid <= high;mid++)
{
if(regex[mid] == '(') ct++ ;
if(regex[mid] == ')') ct-- ;
if(ct == 0) break ;
}
P ret1 = construct(regex,low + 1,mid) ;
if(regex[mid + 1] == '|')
{
P ret2 = construct(regex,mid + 2,high - 1) ;
g[start][ret1.first] = g[start][ret2.first] = 1 ;
g[ret1.second][end] = g[ret2.second][end] = 1 ;
}
else if(regex[mid + 1] == '*')
{
g[start][ret1.first] = g[start][end] = 1 ;
g[ret1.second][end] = g[end][start] = 1 ;
}
else
{
P ret2 = construct(regex,mid + 1,high - 1) ;
g[start][ret1.first] = g[ret1.second][ret2.first] = 1 ;
g[ret2.second][end] = 1 ;
}
return P(start,end) ;
}
void mul(int a[MAXN][MAXN],int b[MAXN][MAXN],int c[MAXN][MAXN],int N)
{
int d[MAXN][MAXN] ;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
d[i][j] = 0 ;
for(int k = 0;k < N;k++)
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
d[i][j] = (d[i][j] + 1LL * a[i][k] * b[k][j]) % MOD ;
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
c[i][j] = d[i][j] ;
}
void power(int a[MAXN][MAXN],int b[MAXN][MAXN],int k,int N)
{
if(k == 0)
{
for(int i = 0;i < N;i++)
for(int j = 0;j < N;j++)
b[i][j] = i == j ? 1 : 0 ;
return ;
}
int c[MAXN][MAXN] ;
power(a,c,k / 2,N) ;
mul(c,c,b,N) ;
if(k % 2 == 1)
{
mul(a,b,b,N) ;
}
}
int solve(char * regex,int L)
{
n = 0 ;
memset(g,0,sizeof g) ;
memset(out,255,sizeof out) ;
P nfa = construct(regex,0,strlen(regex) - 1) ;
for(int i = 0;i < n;i++) g[i][i] = 1 ;
for(int k = 0;k < n;k++)
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
if(g[i][k] && g[k][j])
g[i][j] = 1 ;
memset(ga,0,sizeof ga) ;
memset(gb,0,sizeof gb) ;
for(int i = 0;i < MAXN;i++) aMask[i].clear(),bMask[i].clear() ;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
{
bool va = false,vb = false ;
for(int k = 0;k + 1 < n;k++)
{
if(g[i][k] && out[k] != -1 && g[k + 1][j])
{
if(out[k] == 0) va = true ;
else vb = true ;
}
}
if(va) ga[i][j] = true ;
if(vb) gb[i][j] = true ;
if(ga[i][j]) aMask[i].insert(j) ;
if(gb[i][j]) bMask[i].insert(j) ;
}
memset(g2,0,sizeof g2) ;
int id = 0 ;
set<int> orig[MAXN],q[MAXN] ;
int sz = 0 ;
map<set<int>,int> mp ;
set<int> start ;
start.insert(nfa.first) ;
q[sz++] = start ;
mp[start] = id++ ;
orig[id - 1] = start ;
for(int i = 0;i < sz;i++)
{
set<int> k = q[i] ;
int kk = mp[k] ;
set<int> a,b ;
for(int j = 0;j < n;j++)
if(k.find(j) != k.end())
{
for(set<int> :: iterator it = aMask[j].begin();it != aMask[j].end();++it) a.insert(*it) ;
for(set<int> :: iterator it = bMask[j].begin();it != bMask[j].end();++it) b.insert(*it) ;
}
if(!mp.count(a))
{
q[sz++] = a ;
mp[a] = id++ ;
orig[id - 1] = a ;
}
g2[kk][mp[a]]++ ;
if(!mp.count(b))
{
q[sz++] = b ;
mp[b] = id++ ;
orig[id - 1] = b ;
}
g2[kk][mp[b]]++ ;
}
// cout << "nodes: " << n << ", " << id << endl ;
int g3[MAXN][MAXN] ;
power(g2,g3,L,id) ;
int ret = 0 ;
for(int i = 0;i < id;i++)
if(orig[i].find(nfa.second) != orig[i].end())
ret = (ret + g3[mp[start]][i]) % MOD ;
return ret ;
}
bool vis[MAXN][MAXN] ;
int _L ;
int cur[MAXN] ;
void dfs(int k,int p)
{
if(vis[k][p]) return ;
vis[k][p] = true ;
for(int i = 0;i < n;i++)
if(g[k][i])
dfs(i,p) ;
if(out[k] != -1 && p < _L && cur[p] == out[k]) dfs(k + 1,p + 1) ;
}
int check()
{
memset(vis,false,sizeof vis) ;
dfs(0,0) ;
return vis[1][_L] ? 1 : 0 ;
}
int generate(int k)
{
if(k == _L) return check() ;
cur[k] = 0 ;
int ret = generate(k + 1) ;
cur[k] = 1 ;
ret += generate(k + 1) ;
return ret ;
}
int solve2(char * regex,int L)
{
_L = L ;
n = 0 ;
memset(g,0,sizeof g) ;
memset(out,255,sizeof out) ;
P nfa = construct(regex,0,strlen(regex) - 1) ;
return generate(0) ;
}
string genRegex(int k)
{
if(k == 1)
{
string s ;
if(rand() % 2 == 0) s.push_back('a') ;
else s.push_back('b') ;
return s ;
}
string s ;
int x = rand() % 3 ;
if(x == 0)
{
s = genRegex(k - 1) ;
s = "(" + s + "*)" ;
}
else
{
int f = 1 + rand() % (k - 1) ;
int se = k - f ;
string s1 = genRegex(f) ;
string s2 = genRegex(se) ;
if(x == 1) s = "(" + s1 + s2 + ")" ;
else s = "(" + s1 + "|" + s2 + ")" ;
}
return s ;
}
void generate2()
{
char in[10] = "in .txt" ;
for(int test = 1;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 50 ;
fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
int k = 28 - rand() % 10 ;
string s = genRegex(k) ;
if(s.size() > 100) while(1) ;
int L = rand() % 1000000000 + 1 ;
fprintf(fout,"%s %d\n",s.c_str(),L) ;
}
}
}
void test()
{
for(int t = 0;t < 100;t++)
{
string s = genRegex(15) ;
cout << s << endl ;
int L = rand() % 12 + 5 ;
char reg[MAXN] = {} ;
for(int i = 0;i < s.size();i++) reg[i] = s[i] ;
int ret1 = solve(reg,L) ;
int ret2 = solve2(reg,L) ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "Failed on: " << s << endl ;
while(1) ;
}
}
}
int pow2(int k)
{
if(k == 0) return 1 ;
int ret = pow2(k / 2) ;
ret = 1LL * ret * ret % MOD ;
if(k & 1) ret = 1LL * ret * 2 % MOD ;
return ret ;
}
int main()
{
// generate2() ; return 0 ;
// test() ; return 0 ;
int runs ;
scanf("%d",&runs) ;
for(int t = 1;t <= runs;t++)
{
int L ;
char regex[MAXN] ;
scanf("%s%d",regex,&L) ;
int ret = solve(regex,L) ;
// cout << "test: " << t << endl ;
// cout << ret << " " << pow2(L) << endl ; continue ;
/*
int ret2 = solve2(regex,L) ;
cout << ret << " " << ret2 << endl ;
if(ret != ret2)
{
cout << "Failed" << endl ;
while(1) ;
}
*/
printf("%d\n",ret) ;
}
return 0 ;
}
In Java :
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class Solution {
static int parseIndex = 0;
static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int cases = scan.nextInt();
for(int cs=0; cs<cases; cs++){
String regex = scan.next();
int length = scan.nextInt();
NFA nfa = parse(regex);
DFA dfa = new DFA(nfa);
long[][] graph = dfa.toAdjacencyMatrix();
graph = power(graph, length);
long words = 0;
for(int end : dfa.ends){
words += graph[dfa.start][end];
}
words %= MOD;
System.out.println(words);
}
}
static long[][] power(long[][] matrix, long power){
if(power == 1)
return matrix;
else if(power % 2 == 0)
return power(multiply(matrix, matrix), power/2);
else
return multiply(matrix, power(multiply(matrix, matrix), power/2));
}
static long[][] multiply(long[][] m1, long[][] m2){
long[][] res = new long[m1.length][m1.length];
for(int i=0; i<m1.length; i++){
for(int j=0; j<m1.length; j++){
long dotProd = 0;
for(int k=0; k<m1.length; k++){
dotProd += m1[i][k] * m2[k][j];
dotProd %= MOD;
}
res[i][j] = dotProd;
}
}
return res;
}
static NFA parse(String regex){
parseIndex = 0;
return new NFA(regex);
}
static class DFA{
int start;
HashSet<Integer> ends = new HashSet<Integer>();
List<DFANode> nodes = new ArrayList<DFANode>();
HashMap<DFANode, Integer> nodeMap = new HashMap<DFANode, Integer>();
public DFA(NFA nfa){
HashSet<DFANode> allNodes = new HashSet<DFANode>();
Queue<DFANode> wipNodes = new LinkedList<DFANode>();
DFANode startNode = new DFANode(nfa.start.findClosure());
startNode.startState = true;
allNodes.add(startNode);
wipNodes.offer(startNode);
while(!wipNodes.isEmpty()){
DFANode node = wipNodes.poll();
HashSet<NFANode> nextState = NFA.nextState(node.state, 'a');
if(!nextState.isEmpty()){
DFANode next = new DFANode(nextState);
node.letterA = next;
if(allNodes.add(next))
wipNodes.offer(next);
}
nextState = NFA.nextState(node.state, 'b');
if(!nextState.isEmpty()){
DFANode next = new DFANode(nextState);
node.letterB = next;
if(allNodes.add(next))
wipNodes.offer(next);
}
if(node.state.contains(nfa.end))
node.endState = true;
}
for(DFANode node : allNodes){
int index = nodes.size();
nodes.add(node);
nodeMap.put(node, index);
if(node.startState)
start = index;
else if(node.endState)
ends.add(index);
}
}
long[][] toAdjacencyMatrix(){
long[][] matrix = new long[nodes.size()][nodes.size()];
for(int i=0; i<nodes.size(); i++){
DFANode node = nodes.get(i);
if(node.letterA != null)
matrix[i][nodeMap.get(node.letterA)] = 1;
if(node.letterB != null)
matrix[i][nodeMap.get(node.letterB)] = 1;
}
return matrix;
}
}
static class NFA{
NFANode start, end;
public NFA(String regex){
start = new NFANode();
end = new NFANode();
end.endState = true;
if(regex.charAt(parseIndex) == 'a'){//direct 'a' transition
parseIndex++;
start.letterA.add(end);
} else if(regex.charAt(parseIndex) == 'b'){//direction 'b' transition
parseIndex++;
start.letterB.add(end);
} else{//opening bracket
parseIndex++;
NFA child = new NFA(regex);
if(regex.charAt(parseIndex) == '*'){//repeat
parseIndex++;
start.epsilon.add(child.start);
start.epsilon.add(end);
child.end.epsilon.add(end);
child.end.endState = false;
end.epsilon.add(child.start);
} else if(regex.charAt(parseIndex) == '|'){//or
parseIndex++;
NFA child2 = new NFA(regex);
start.epsilon.add(child.start);
start.epsilon.add(child2.start);
child.end.epsilon.add(end);
child2.end.epsilon.add(end);
child.end.endState = false;
child2.end.endState = false;
} else{//concat
NFA child2 = new NFA(regex);
start = child.start;
end = child2.end;
child.end.epsilon.add(child2.start);
child.end.endState = false;
}
parseIndex++;//skip closing bracket
}
}
static HashSet<NFANode> nextState(HashSet<NFANode> states, char transition){
HashSet<NFANode> reachableClosure = new HashSet<NFANode>();
for(NFANode node : states){
HashSet<NFANode> reachable = new HashSet<NFANode>();
switch(transition){
case 'a':
reachable.addAll(node.letterA);
break;
case 'b':
reachable.addAll(node.letterB);
break;
}
for(NFANode n : reachable)
reachableClosure.addAll(n.findClosure());
}
return reachableClosure;
}
}
static class NFANode{
HashSet<NFANode> letterA = new HashSet<NFANode>();
HashSet<NFANode> letterB = new HashSet<NFANode>();
HashSet<NFANode> epsilon = new HashSet<NFANode>();
boolean endState = false;
HashSet<NFANode> findClosure(){
HashSet<NFANode> closure = new HashSet<NFANode>();
Stack<NFANode> DFS = new Stack<NFANode>();
DFS.push(this);
while(!DFS.isEmpty()){
NFANode node = DFS.pop();
closure.add(node);
for(NFANode n : node.epsilon)
if(!closure.contains(n))
DFS.push(n);
}
return closure;
}
}
static class DFANode{
DFANode letterA;
DFANode letterB;
HashSet<NFANode> state = new HashSet<NFANode>();
boolean startState = false;
boolean endState = false;
public DFANode(HashSet<NFANode> state){
this.state = state;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((state == null) ? 0 : state.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DFANode other = (DFANode) obj;
if (state == null) {
if (other.state != null)
return false;
} else if (!state.equals(other.state))
return false;
return true;
}
}
}
In Python3 :
from enum import Enum
from collections import namedtuple
Edge = namedtuple('Edge', 'dest char')
class Alphabet(Enum):
a = 'a'
b = 'b'
e = None
def empty_edge(dest):
return Edge(dest, Alphabet.e)
class CountStrings:
def __init__(self, regex_string):
RegexGraphNFA.node_count = 0
self.regex_string = regex_string
nfa_graph = self.translate_regex()
translate_graph = TranslateGraph(nfa_graph)
self.dfa_graph = translate_graph.translate()
def calculate(self, string_length):
return self.dfa_graph.count_paths(string_length)
def translate_regex(self, index=0):
result_set = ResultSet()
while index < len(self.regex_string):
if self.regex_string[index] == '(':
out_list, index = self.translate_regex(index + 1)
result_set.insert(out_list)
elif self.regex_string[index] == ')':
result = result_set.calculate_result()
return result, index
elif self.regex_string[index] == '|':
result_set.set_or()
else:
result_set.insert(self.regex_string[index])
index += 1
return result_set.calculate_result()
class ResultSet:
def __init__(self):
self.r1 = None
self.r2 = None
self.has_or = False
def set_or(self):
self.has_or = True
def calculate_result(self):
repeat = True if self.r2 == '*' else False
if self.r2 is None:
pass
elif repeat:
self.calculate_repeat()
elif self.has_or:
self.calculate_or()
else:
self.calculate_and()
return self.r1
def calculate_repeat(self):
self.r1.graph_repeat()
def calculate_or(self):
self.r1.graph_or(self.r2)
def calculate_and(self):
self.r1.graph_add(self.r2)
def insert(self, value):
if value != '*' and isinstance(value, str):
value = RegexGraphNFA.get_char_graph(Alphabet[value])
if self.r1 is None:
self.r1 = value
else:
self.r2 = value
class RegexGraphNFA:
node_count = 0
def __init__(self):
self.edges = None
self.head = None
self.tail = None
@staticmethod
def get_char_graph(value):
my_graph = RegexGraphNFA()
my_graph.insert_char(value)
return my_graph
@classmethod
def get_next_node_id(cls):
node_id = cls.node_count
cls.node_count += 1
return node_id
def insert_char(self, value):
self.head = self.get_next_node_id()
self.tail = self.get_next_node_id()
self.edges = {self.head: [Edge(self.tail, value)],
self.tail: []}
def graph_add(self, other):
join_node = self.get_next_node_id()
self.join(other)
self.edges[self.tail].append(empty_edge(join_node))
self.edges[join_node] = [empty_edge(other.head)]
self.tail = other.tail
def graph_repeat(self):
new_head = self.get_next_node_id()
new_tail = self.get_next_node_id()
self.edges[self.tail].extend([empty_edge(self.head), empty_edge(new_tail)])
self.edges[new_head] = [empty_edge(self.head), empty_edge(new_tail)]
self.edges[new_tail] = []
self.head = new_head
self.tail = new_tail
def graph_or(self, other):
new_head = self.get_next_node_id()
new_tail = self.get_next_node_id()
self.join(other)
self.edges[new_head] = [empty_edge(self.head), empty_edge(other.head)]
self.edges[self.tail].append(empty_edge(new_tail))
self.edges[other.tail].append(empty_edge(new_tail))
self.edges[new_tail] = []
self.head = new_head
self.tail = new_tail
def join(self, other):
for node, edge in other.edges.items():
if node in self.edges:
self.edges[node].extend(edge)
else:
self.edges[node] = edge
def get_dfa_char_node_set(self, origin, use_char):
node_set = set()
for my_node in origin:
for edges in self.edges[my_node]:
if edges.char == use_char:
node_set.add(edges.dest)
return self.get_dfa_zero_node_set(node_set)
def get_dfa_zero_node_set(self, origin):
node_set = set(origin)
processed = set()
while len(node_set.difference(processed)) > 0:
my_node = node_set.difference(processed).pop()
for edges in self.edges[my_node]:
if edges.char == Alphabet.e:
node_set.add(edges.dest)
processed.add(my_node)
return frozenset(node_set)
class TranslateGraph:
language = (Alphabet.a, Alphabet.b)
def __init__(self, nfa_graph: RegexGraphNFA):
self.node_count = 0
self.nfa_graph = nfa_graph
self.trans_to = {}
self.trans_from = {}
self.table = {}
def get_next_node_id(self):
node_id = self.node_count
self.node_count += 1
return node_id
def add_translate(self, nfa_ids):
if len(nfa_ids) == 0:
return None
if nfa_ids not in self.trans_from:
dfa_id = self.get_next_node_id()
self.trans_to[dfa_id] = nfa_ids
self.trans_from[nfa_ids] = dfa_id
self.table[dfa_id] = dict(zip(self.language, [None] * len(self.language)))
return self.trans_from[nfa_ids]
def translate(self):
self.create_translate_table()
return self.build_dfa()
def build_dfa(self):
head = 0
valid_ends = set()
adjacency = {}
for node, edges in self.table.items():
adjacency[node] = []
if self.nfa_graph.tail in self.trans_to[node]:
valid_ends.add(node)
for my_char, node_dest in edges.items():
if node_dest is not None:
adjacency[node].append(Edge(node_dest, my_char))
return RegexGraphDFA(head, valid_ends, adjacency)
def create_translate_table(self):
nfa_ids = self.nfa_graph.get_dfa_zero_node_set({self.nfa_graph.head})
self.add_translate(nfa_ids)
processed = set()
while len(set(self.table).difference(processed)) > 0:
my_node = set(self.table).difference(processed).pop()
for char in self.language:
next_nodes = self.nfa_graph.get_dfa_char_node_set(self.trans_to[my_node], char)
dfa_id = self.add_translate(next_nodes)
self.table[my_node][char] = dfa_id
processed.add(my_node)
class RegexGraphDFA:
def __init__(self, head, valid_ends, edges):
self.edges = edges
self.head = head
self.valid_ends = valid_ends
self.edge_matrix = Matrix.get_from_edges(len(self.edges), self.edges)
def count_paths(self, length):
modulo = 1000000007
edge_walk = self.edge_matrix.pow(length, modulo)
count = 0
for end_node in self.valid_ends:
count += edge_walk.matrix[self.head][end_node]
return count % modulo
class Matrix:
@staticmethod
def get_from_edges(dimension, adj_list):
my_matrix = Matrix.get_zeros(dimension)
my_matrix.add_edges(adj_list)
return my_matrix
@staticmethod
def get_zeros(dimension):
my_matrix = Matrix(dimension)
my_matrix.pad_zeros()
return my_matrix
def copy(self):
my_matrix = Matrix(self.dimension)
my_matrix.matrix = []
for i in range(self.dimension):
my_matrix.matrix.append([])
for j in range(self.dimension):
my_matrix.matrix[i].append(self.matrix[i][j])
return my_matrix
def __init__(self, dimension):
self.matrix = None
self.dimension = dimension
def __str__(self):
my_str = ''
for row in self.matrix:
my_str += str(row) + "\n"
return my_str
def pad_zeros(self):
self.matrix = []
for i in range(self.dimension):
self.matrix.append([])
for j in range(self.dimension):
self.matrix[i].append(0)
def add_edges(self, adj_list):
if adj_list is not None:
for from_node, edge_list in adj_list.items():
for to_node, my_char in edge_list:
self.matrix[from_node][to_node] = 1
def pow(self, pow_val, mod_val=None):
started = False
target = pow_val
current_pow = 1
current_val = 0
while pow_val > 0:
if current_pow == 1:
current_pow_matrix = self.copy()
else:
current_pow_matrix = current_pow_matrix.mat_square_mult(current_pow_matrix, mod_val)
if pow_val % (2 * current_pow):
current_val += current_pow
if started:
result = result.mat_square_mult(current_pow_matrix, mod_val)
else:
result = current_pow_matrix.copy()
started = True
# print(current_pow, current_val, target)
pow_val -= current_pow
current_pow *= 2
return result
def mat_square_mult(self, other, mod_val=None):
result = Matrix.get_zeros(self.dimension)
for i in range(self.dimension):
for j in range(self.dimension):
val = 0
for k in range(self.dimension):
val += self.matrix[i][k] * other.matrix[k][j]
if mod_val is not None:
val %= mod_val
result.matrix[i][j] = val
return result
def main():
cases = int(input().strip())
for i in range(cases):
in_line = input().strip().split()
my_class = CountStrings(in_line[0])
print(my_class.calculate(int(in_line[1])))
if __name__ == "__main__":
main()
View More Similar Problems
Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function
View Solution →Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →
