Inverting a Binary Tree with Scala

The problem of Inverting a Binary Tree has got some hype after following tweet.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

— Max Howell (@mxcl) June 10, 2015

As a problem-solver, I was wondering how to approach this problem, as it seems to be a great application of structural recursion. In this post, let’s see how to solve it with functional programming and Scala.

Problem Definition:

The problem can be specified as follows.

Given a Binary Tree t1:

	4
	/ \
	2 7
	/ \ / \
	1 3 6 9

view raw actual-tree.txt hosted with ❤ by GitHub

We have to implement a function to transform t1 to a Binary Tree t2:

	4
	/ \
	7 2
	/ \ / \
	9 6 3 1

view raw invertedTree.txt hosted with ❤ by GitHub

Thus the function invertTree essentially has following signature.

$invertTree: Tree => Tree$

Solution

First, we define a Binary Tree ADT.

	sealed trait Tree[+A]
	case object EmptyTree extends Tree[Nothing]
	case class Node[A](value: A , left: Tree[A], right: Tree[A]) extends Tree[A]

view raw BinaryTree.scala hosted with ❤ by GitHub

In order to conveniently encode tree instances, we add following methods in the companion object of Tree.

	object Tree{
	def empty[A]: Tree[A] = EmptyTree
	def node[A](value: A, left: Tree[A] = empty, right: Tree[A] = empty): Tree[A]
	= Node(value, left, right)
	}

view raw BinaryTree.scala hosted with ❤ by GitHub

As a result, we can define an instance of a tree in Scala REPL as follows.

	scala> val t1 = node(4,
	node(2
	, node(1)
	, node(3)
	) ,
	node(7
	, node(6)
	, node(9)
	)
	)

	t1: Tree[Int] =
	Node(4,
	Node(2,
	Node(1,EmptyTree,EmptyTree),
	Node(3,EmptyTree,EmptyTree)),
	Node(7,
	Node(6,EmptyTree,EmptyTree),
	Node(9,EmptyTree,EmptyTree)))

view raw BinaryTree.scala hosted with ❤ by GitHub

Next, in order to facilitate structural recursion, we define fold function for the binary tree as follows:

	def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B): B = t match {
	case EmptyTree => z
	case Node(x,l,r) => f ( fold( l , z )(f) , x , fold( r , z )(f) )
	}

view raw fold.scala hosted with ❤ by GitHub

It allows to traverse the tree, perform transformations and accumulate the result. For instance, we can define a function to count the length of the tree in a generic manner–

	def size[T] (tree: Tree[T]) =
	fold(tree, 0: Int){(l,x,r) => l + r + 1}

	scala> size(t1)
	res11: Int = 7

view raw BinaryTree.scala hosted with ❤ by GitHub

Also, we can define a map function that applies a function f: A ⇒ B on the value of each Node. Note that the application of map is always structure-preserving, that is, it retains the existing shape as it was before application (unlike the aforementioned size function) and perform only local transformations.

	import Tree._

	def map[A,B](tree: Tree[A])(f: A => B): Tree[B] =
	fold(tree, Tree.empty[B]){(l, x, r) => Node(f(x), l,r)}



	scala> map (t1) ( x => x * 10)
	res11: Tree[Int] =
	Node(40,
	Node(20,
	Node(10,EmptyTree,EmptyTree),
	Node(30,EmptyTree,EmptyTree)),
	Node(70,
	Node(60,EmptyTree,EmptyTree),
	Node(90,EmptyTree,EmptyTree)))

view raw BinaryTree.scala hosted with ❤ by GitHub

As you have guessed, we can similarly define the invertTree function in a generic manner as follows:

	def invertTree[A](tree: Tree[A]): Tree[A] =
	fold (tree, Tree.empty[A]){(leftT, value, rightT) => Node(value, rightT, leftT)}

view raw BinaryTree.scala hosted with ❤ by GitHub

In essence, invertTree simply swaps left node with the right node, and thus derives the resultant tree with the generic fold.

	scala> invertTree(t1)
	res12: Tree[Int] =
	Node(4,
	Node(7,
	Node(9,EmptyTree,EmptyTree),
	Node(6,EmptyTree,EmptyTree)),
	Node(2,
	Node(3,EmptyTree,EmptyTree),
	Node(1,EmptyTree,EmptyTree)))

	/*
	4
	/ \
	7 2
	/ \ / \
	9 6 3 1

	*/

view raw BinaryTree.scala hosted with ❤ by GitHub

Neat..uh? By the way, this problem can be solved in several ways. This post particularly demonstrates the application of structural recursion in a generic manner (e.g., with fold), which is the essence of #fp, imho ;).

If you have any question/suggestion or a different idea to solve this problem, please free to post it as a comment; I highly appreciate that! Thanks for visiting!

References

LeetCode OJ: Invert Binary Tree

UVa 10664. Luggage

The UVa 10664: Luggage is a typical example of the problems that can be solved using dynamic programming (DP) technique. In fact, after further analysis, this problem can be realized as a special case of Subset-Sum problem, which we have discussed in a recent post.

The following Java code snippet outlines an algorithm using dynamic programming to solve this problem. Notice that the function solveLuggageProblem applies a bottom-up DP to construct dpTable. The boolean value of each dpTable[i][j] implies that whether it is possible to achieve weight j from the weights of 1..i suitcases. In this way, it determines whether halfWeight — the half of the total weights (of the suitcases)– can be derived from using 1..n suitcases, i.e., whether the weights of suitcases can be distributed equally into the boots of two cars.

	import java.io.PrintWriter;
	import java.util.Scanner;

	class Main {

	private final Scanner in;
	private final PrintWriter out;

	public Main(){
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out){
	this.in = in;
	this.out = out;
	}

	private static int[] readLineAsIntegers(String input){
	String [] ints = input.trim().split(" ");
	int [] rets = new int[ints.length];

	for (int i = 0 ;i < ints.length; i++)
	rets[i] = Integer.parseInt(ints[i]);

	return rets;
	}

	private String solveLuggageProblem(int[] weights){
	final String _TRUE = "YES";
	final String _FALSE = "NO";

	int totalWeight = getTotalWeight(weights);

	if (totalWeight%2 != 0)
	return _FALSE;

	int n = weights.length+1;
	int halfWeight = totalWeight/2;

	boolean [][] dpTable = new boolean [n][halfWeight+1];

	// Base case 1: weights = 0 for all n --> True
	for(int i = 0;i<n;i++)
	dpTable[i][0] = true;

	// Base case 2: weights !=0 for all n=0 --> False
	for(int i = 1;i<halfWeight+1;i++)
	dpTable[0][i] = false;

	for (int i = 1; i< n; i++ ){

	for (int j = 1; j< halfWeight+1; j++){

	int w_i = weights[i-1]; // weight of ith item

	if(j<w_i) // this item can't be included since its over the limit:j
	dpTable[i][j] = dpTable[i-1][j];
	else
	dpTable[i][j] = dpTable[i-1][j] \|\| dpTable[i-1][j-w_i];
	}
	}

	return dpTable[n-1][halfWeight]==true?_TRUE:_FALSE;

	}

	private int getTotalWeight(int[] weights) {
	int totalWeight = 0;
	// compute total weight of the bags
	for(int indx =0;indx< weights.length;indx++){
	totalWeight += weights[indx];
	}
	return totalWeight;
	}

	public void run(){
	final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases

	for (int i = 0 ; i< T ; i++){
	int [] weights = readLineAsIntegers(in.nextLine());

	// result:
	out.println(solveLuggageProblem(weights));
	}
	}


	public static void main(String[] args) {

	Main solveLuggageProblem = new Main();
	solveLuggageProblem.run();
	}

	}

view raw uva10664.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

Background: Collatz Conjecture

Collatz problem, also known as problem, concerns the iterates generated by the repeated applications of following the function: Given a positive integer, —

which implies that if is even, it returns , otherwise . This function is called Collatz function. Consider, for instance, , the generated iterates are following:. This sequence is referred to as Collatz sequence, or hailstone numbers.

Collatz conjecture, which is credited to Luther Collatz at the University of Hamburg, asserts that for any positive integer , the repeated applications of the Collatz function, i.e., eventually produces value ; that is, , where denotes application of . Considering , it follows: .

The generated sequence of iterates: is called the Collatz-trajectory of . For instance, beginning from , the resulted sequence converged to as follows: . Therefore, Collatz-trajectory of 26 is . Note that, although Collatz problem is based on this simple concept, it is intractably hard. So far, it has been verified for by Leaven and Vermeluen.

Algorithm Design: 3n+1 problem

In the rest of this post, we intend to solve the problem, which is essentially a restricted or bounded version of the Collatz problem.

Interpretation. It restricts the iteration by exiting as soon as the Collatz sequence reaches to value 1 at . For = 26, the resulting Collatz sequence is therefore: , and length of the sequence is i.e., 11. This problem asks to compute the largest Collatz sequence that results from any integer between and , which are provided as inputs. Note that, the value of and are both positive integers: .

Implementation. We first apply a naïve brute-force algorithm to solve this problem, which computes the length of the sequence for each integer from to , and returns the maximum length found. It is worth noting that-

A naïve brute-force algorithm redundantly computes sequences again and again. Consider =13 and =26. For = 26, we also compute the sequence for 13 that has already been computed during = 13.

We must apply a tail-recursive implementation to compute the sequence, as naïve implementation might results in stack overflow.

As we shall see next, we have optimized the naïve implementation considering the above observations. First, we define function, nextCollatz, that returns next integer of the Collatz sequence, given an integer . In effect, it computes from as follows.

	let nextCollatz (n:int64) =
	if n%2L = 0L then n/2L else 3L*n+1L

view raw gistfile1.fs hosted with ❤ by GitHub

Using the algorithm outlined in collatzSeqLength, the length of the Collatz sequence is computed for any given integer .

	let max = 1000001L
	let memo = Array.create (max\|>int) 0L

	// Computes Collatz sequence length, given a
	// positive integer, x.
	let rec collatzSeqLength (x:int64):int64 =
	let rec seqLength' (n:int64) contd =
	match n with
	\| 1L -> contd 1L // initalizing sequence length with 1
	\| _ ->
	if n < max && memo.[n\|>int] <> 0L then
	contd memo.[n\|>int]
	else
	seqLength' (nextCollatz n) (fun x ->
	let x' = x+1L //incrementing length and storing it in memo.
	if n<max then
	memo.[n\|>int] <- x'
	else
	()
	contd x'
	)
	x\|>(fun i -> seqLength' i id)

view raw gistfile1.fs hosted with ❤ by GitHub

It includes the following optimizations over the naïve implementation we stated earlier:

Memorization has been incorporated to effectively optimize the algorithm by avoiding redundant computations of the sequence and its length, which in turn provides a faster algorithm than its naïve counterpart, albeit with the cost of additional space.

Tail-recursive algorithm enables computation of Collatz sequence with larger .

Continuation-passing-style has been applied in this algorithm to accommodate, and to combine tail-call optimization with memorization.

The following snippet demonstrates how the maximum sequence length is obtained by invoking collatzSeqLength for each integer between the given and .

	let maxCollazSeqLength (x:int64,y:int64) =
	let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)

	seq[x'..y']
	\|> Seq.fold (fun max x ->
	let r = collatzSeqLength x
	if r > max then r else max) 0L

view raw gistfile1.fs hosted with ❤ by GitHub

Complete source code of this problem can be found in this gist. Following IDEONE page (with sample inputs and outputs) has been provided to further play with the code (in case of the unavailability of F# in local system). Java source code is also available for this problem.

Try solving Euler Problem 14, which resembles this problem and based on these stated concepts. Please leave a comment if you have any question/suggestion regarding this post. Happy coding!

Background¶

This problem is a special case of Knapsack problem. Main objective of this problem is to select a subset of parties that maximizes fun value, subject to the restriction that the budget must not exceed .

More formally, we are given a budget as the bound. All parties have costs and values . We have to select a subset such that is as large as possible, and subject to the following restriction —

Furthermore, an additional constraint: “do not spend more money than is absolutely necessary” is applied, which implies following. Consider two parties and ; if and , then we must select instead of .

Algorithm¶

Attempt 1

The definition of this problem suggests a recursive solution. However, a naïve recursive solution is quite impractical in this context, as it requires exponential time due to the following reason: a naïve recursive implementation applies a top-down approach that solves the subproblems again and again.

Attempt 2

Next, we select dynamic programming technique to solve this problem. So, we have to define a recurrence that expresses this problem in terms of its subproblems, and therefore it begs the answer of the following question:

What are the subproblems? We have two variants: and , i.e. available budget and number of parties. We can derive smaller subproblems, by modifying these variants; accordingly, we define-

It returns the maximum value over any subset where . Our final objective is to compute , which refers to the optimal solution, i.e., maximal achievable fun value from budget and parties.

To define the recurrence, we describe in terms of its smaller subproblems.

How can we express this problem using its subproblems? Let’s denote to be the optimal subset that results in . Consider party and note following.

It , then . Thus, using the remaining budget and the parties , we seek the optimal solution.
Otherwise, then . Since is not included, we haven’t spent anything from .

Obviously, when , we apply the 2nd case. Using the above observations, we define the recurrence as follows–

where the base conditions can be rendered as below.

Using the above recurrence, we can compute for all parties and for costs . In essence, we build the OPT table, which consists of rows and columns, using a bottom-up approach as stated in the following algorithm.

	Initialize OPT[0,c] = 0, for c = 0..C and OPT[i,0], for i= 0..n
	For i = 1,...,n do
	For c = 1,..,C do
	Use above recurrence to compute OPT(i,c)
	Return OPT(n,C)

view raw gistfile1.txt hosted with ❤ by GitHub

Implementation¶

Following code builds the OPT table using the stated algorithm.

	let computeOptPartySchedule (budget,N,(costs:int[]),(funValues:int[])) =
	let OPT = Array2D.zeroCreate (N+1) (budget+1)

	for i = 1 to N do
	for j = 0 to budget do
	let c_i = costs.[i-1] //cost for the ith party
	let f_i = funValues.[i-1] // fun value associated with ith party

	OPT.[i,j] <-
	match j,c_i with
	\| _ when j<c_i -> OPT.[i-1,j]
	\| _ -> Math.Max(OPT.[i-1,j],f_i + OPT.[i-1, j-c_i])

	// returning (1) summation of all entrance fee or costs,
	// (2) summation of fun values
	((budget,N,OPT,OPT.[N,budget])\|>computeOptCost, OPT.[N,budget])

view raw gistfile1.fs hosted with ❤ by GitHub

In effect, it does two things: builds OPT table and afterwards, returns the OPT(n,C) and associated optimal cost (due to the constraint “do not spend more money than is absolutely necessary” discussed in background section) as a tuple (see Line 16). Following function computes the optimal cost.

	let computeOptCost (budget,N,(opt:int [,]),optFunValue) =
	let mutable optCost = 0
	for c=budget downto 0 do
	if opt.[N,c] = optFunValue then
	optCost <- c
	else
	()
	optCost

view raw gistfile1.fs hosted with ❤ by GitHub

Complexity. as each requires time.

For the complete source code, please check out this gist, or visit its IDEONE page to play with the code. Please leave a comment if you have any question or suggestion regarding the algorithm/implementation.

Happy coding!

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

	class Main {
	public static void main(String[] args) throws Exception{
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out, true);

	while(in.hasNextInt()){
	int i = in.nextInt();
	int j = in.nextInt();

	int from = Math.min(i, j);
	int to = Math.max(i, j);

	int max = 0;

	for (int ii = from;ii<=to;ii++){
	max = Math.max(max, computeCycleLength(ii));
	}

	out.printf("%d %d %d\n", i, j, max);
	}

	}

	private static int computeCycleLength(long n) {

	if (n==1)
	return 1;
	if (n<_MaxValue && memo[(int)n] != 0)
	return memo[(int)n];

	// computing length of collatz cycle
	int len = 1 + computeCycleLength(nextCollatz(n));

	// storing it in cache
	if (n<_MaxValue)
	memo[(int)n] = len;
	return len;
	}


	private static int _MaxValue = 1000000;
	public static int[] memo = new int[_MaxValue];

	public static long nextCollatz(long n){

	if (n%2==0)
	return n/2;
	else
	return n*3+1;
	}
	}

Tag: problem-solving

Inverting a Binary Tree with Scala

Problem Definition:

Solution

References

UVa 10664. Luggage

See Also

UVa 100. The 3n+1 Problem: Solving with a Brute-force Algorithm

See Also

Collatz Problem a.k.a. 3n+1 Problem

Background: Collatz Conjecture

Algorithm Design: 3n+1 problem

See Also

SPOJ 97. Party Schedule (PARTY) with F#

Background¶

Algorithm¶

Attempt 1

Attempt 2

Implementation¶

See Also