# Posts tagged Recursion

## Nth Element of a BST

0

This question seems very straight forward on the surface but an efficient solution is tricky to implement in Java due to pass-by-value semantics. Read on to see why!

Question:

Given a BST of integer elements, return the nth element as quickly as possible. Counting starts at 1 (not 0).

Input (input.txt):

4
3
-1
15
2
7
16

Output (stdout):

7

Solution:

A very naive solution is to traverse through the entire tree in-order, adding each element to an ArrayList as you go, and returning the nth element of the resulting ArrayList. This solution is simple to implement but uses extra memory and has a wasteful run-time if n is small compared to the size of the tree (although the run-time can be improved via early termination).

A better idea is to perform the recursive in-order traversal on the tree nodes while keeping a global counter that we can modify across the recursion stack. (Note that we need to define a custom wrapper object for this counter to simulate pass-by-reference of primitive values.) As far as the search logic goes, we can terminate the search and return the result as soon as the counter is fully decremented from n to 0. One final trick: we need to use the Integer primitive wrapper so we can return a null value when the nth element is not found in a substree.

```    public static void main (String [] args) throws IOException {
Scanner in = new Scanner (new FileReader("src/input.txt"));
int n = in.nextInt();
BSTNode root = new BSTNode(in.nextInt());
while(in.hasNext()) {
root.insert(new BSTNode(in.nextInt()));
}
System.out.println(findNthElement(root,new Counter(n)));
}

static Integer findNthElement(BSTNode node, Counter counter) {
//If we reached the end of subtree return null to indicate "not found in subtree"
if(node==null )  {
return null;
}
//Traverse left subtree
Integer result = findNthElement(node.left, counter);
//Return result if found in left subtree
if (result!=null) {
return result;
}
//In-order visit
counter.value=counter.value-1;
//Return node value if found
if(counter.value == 0) {
return node.value;
}
//Traverse right subtree
result = findNthElement(node.right, counter);
return result;
}

static class Counter {
int value;
public Counter(int value) {
this.value = value;
}
}

static class BSTNode {
BSTNode left;
BSTNode right;
int value;

public BSTNode(int value) {
this.value = value;
}

//Standard BST insertion algorithm
public void insert(BSTNode node) {
if(node.value<value) {
if (left==null) {
left = node;
} else {
left.insert(node);
}
}
if(node.value>value) {
if (right == null) {
right = node;
} else {
right.insert(node);
}
}
}
}
```

## A Simple Regex Matcher

0

This is a classic technical interview question which tests knowledge of string manipulation and recursion.

Question:

Given a regex expression and a string, return true if the regex matches the string. The rules:

• Strings are composed of alphanumeric characters.
• Regexes are composed of alphanumeric characters and 2 special characters ‘.’ and ‘*’.
• A regex matches a string if every character in the regex matches every character in the string.
• Two single characters match if they are equal.
• The special character ‘.’ matches with any single character.
• If the special character ‘*’ appears in the regex, then for our string we can match 0 or more contiguous occurrences of the character preceding the ‘*’. For example, “a*bc” matches “aaabc”.
• For “.*”, we can match 0 or more contiguous occurrences of any character. For example, “.*bc” matches “xyzbc”.
• A pair of quotes (“”) denotes an empty string.

Input (input.txt):

a a
abc abc
a.c axc
a*bc aaabc
a*bc bc
.*bc xyzbc
a*aa aaaa
aa aaa
aaa aa
a* “”

Output (stdout):

true
true
true
true
true
true
true
false
false
true

Solution:

The basic idea is to attempt to match the start of the regex with the start of the string and recursively match the remaining regex against the remaining string.

```    public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("src/input.txt"));
while (in.hasNextLine()) {
String regex = in.next();
String string = in.next();
//Special handling of empty strings
if(regex.equals("\"\"")){
regex="";
}
if(string.equals("\"\"")){
string="";
}
System.out.println(regexMatchesString(regex, string));
}
}

static boolean regexMatchesString (String regex, String string) {
if(regex.equals("") && string.equals("")) {
//Base case when regex matches string.
return true;
} else if (regex.equals("")) {
//Base case when string exceeds regex.
return false;
} else {
//Attempt to match start of regex with start of string.
if(regex.length()>1 && regex.charAt(1)=='*') {
//Handle wild card:
//a)Try ignoring wild card.
boolean matched = regexMatchesString (regex.substring(2), string);
if (matched) {
return true;
}
//b)Try consuming one or more matching characters.
for (int i=0;i<string.length();i++) {
if (matches(regex.charAt(0), string.charAt(i))) {
matched = regexMatchesString (regex.substring(2), string.substring(i+1));
if (matched) {
return true;
}
} else {
return false;
}
}
//Remaining regex does not match remaining string.
return false;
} else if (string.equals("")) {
//Base case when regex exceeds string.
return false;
} else if (matches(regex.charAt(0), string.charAt(0))) {
//Try consuming a single character.
return regexMatchesString (regex.substring(1), string.substring(1));
} else {
//Start of regex does not match start of string.
return false;
}
}
}

//Returns whether a single regex character matches a single string character.
static boolean matches (char regexChar, char stringChar) {
return regexChar == '.' || regexChar == stringChar;
}
```

The trickiest part of this solution is how the wildcard is handled – we must test all n+1 cases of consuming 0 to n matching characters with our wild card since it not necessarily the case that we want to consume all matching characters. (Ex. “a*ab” should match “aab” – the “a*” only consumes a single “a” in this case.)

Go to Top