Java Daily Coding Problem #008
Andrew ・11 min read
Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Java, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!
Problem
A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value.
Given the root to a binary tree, count the number of unival subtrees.
For example, the following tree has 5 unival subtrees:
0 / \ 1 0 / \ 1 0 / \ 1 1
Strategy
Spoilers! Don't look below unless you want to see my solution!
Jargon: A binary tree is a tree data structure made of nodes, where each node can have 0, 1, or 2 child nodes. Child nodes are connected to their parent nodes by edges. A child node only ever has a single parent node. When traversing the tree by travelling along its edges, a parent node is always closer to the root node than its child nodes (by 1 edge).
If a parent node has two child nodes, they are ordered and referred to as the left child and the right child. A node's children and its children's children, etc. are that node's descendants, while its parent and its parent's parent, etc. are that node's ancestors.
Left and right nodes can be referred to as sibling nodes. Nodes with no children are leaves. Nodes with no parents are root nodes (or, rarely, orphan nodes). A subtree is a portion of a larger binary tree, which comprises a particular node of the original tree and all of that node's descendants. Note that a subtree is itself a binary tree, so all of the above nomenclature can be applied to it, as well.
The problem statement says that the example tree has five unival subtrees. So it must be counting the leaves (nodes with no children) as unival subtrees. The first thing we can do, then, is simply get the number of leaves in the tree. The number of leaves puts a lower bound on the number of unival subtrees.
The next thing we need to do is look at nodes that aren't leaves and flag them Integer unival = <0 or 1>
if they are the root node of unival subtrees and 1
otherwise. We need four states  (1) undetermined unival status, (2) determined and 0unival, (3) determined and 1unival, (4) determined and not unival.
So we start by building a binary tree where each node has a property unival
and initialise all nodes to unival = null
(undetermined status). Then, we can write a loop that starts with the root node of the tree and does something like:
 Check if
this.unival
isnull
for this node. If
this.unival
isnull
for this node, we haven't yet determined this node's subtree's unival status; go to (2).  If
this.unival
is notnull
for this node, attempt to move to this node's parent. If this node has a parent, refocus on the parent node, then go to the start of step (1).
 If this node doesn't have a parent, we're done! If this node has no parent, then it is the root node of the entire binary tree. If we know its unival status, then we must know the unival status of every one of its descendant nodes.
 If
 To check if a subtree is unival, we must check the unival status of its root node's children (of which there can be 0, 1, or 2 in a binary tree.
 If this node has 0 children, this subtree is unival. Set
this.unival =
this node's value and go to (1b).  If this node has 1 child, check the unival status of that child
 If the child's unival status is non
null
, set the parent's unival status by examining its value and its child's value, then move to step (1b)  If the child's unival status is
null
, refocus on that child node, then go to step (1a).
 If the child's unival status is non
 If this subtree's root node has 2 children, check the unival status of the left child node
 If the left node's unival status is non
null
, check the unival status of the right node If the right node's unival status is non
null
, we can determine its parent's unival status from the status of these two nodes. Set it, then move to step (1b).  If the right node's unival status is
null
, refocus on that node, then go to step (1a).
 If the right node's unival status is non
 If the left node's unival status is
null
, refocus on that node, then go to step (1a).
 If the left node's unival status is non
 If this node has 0 children, this subtree is unival. Set
So we start at the root node of the tree, and work our way down the left side of the tree until we arrive at a leaf. We then "fill in" the tree from lefttoright, bottomtotop until we end up back at the root node. At that point, we have all of the unival
statuses set to either 1
, 0
, or 1
, and we can simply count the number of unival > 1
nodes to get the total number of unival subtrees in the tree.
Code
Before we do anything with unival subtrees, we need a binary tree data structure. It's not difficult to code one of these from scratch, so let's do that. First, we have a generic BinaryNode
class (using a Builder pattern):
package DCP;
public class BinaryNode {
public static class Builder {
private Integer value = null;
private BinaryNode left = null;
private BinaryNode right = null;
private BinaryNode parent = null;
private Boolean parentHasLeft = null;
private Boolean parentHasRight = null;
public Builder (Integer value) {
this.value = value;
}
public Builder left (BinaryNode left) {
if (left.parent() != null)
throw new IllegalStateException(
"ERROR: left node already has a parent");
this.left = left;
return this;
}
public Builder right (BinaryNode right) {
if (right.parent() != null)
throw new IllegalStateException(
"ERROR: right node already has a parent");
this.right = right;
return this;
}
public Builder parent (BinaryNode parent) {
if (parent == null) return this;
this.parentHasLeft = (parent.left() != null);
this.parentHasRight = (parent.right() != null);
if (this.parentHasLeft && this.parentHasRight)
throw new IllegalStateException(
"ERROR: parent already has two children");
this.parent = parent;
return this;
}
public BinaryNode build() {
BinaryNode node = new BinaryNode(this.value);
node.left = this.left;
node.right = this.right;
node.parent = this.parent;
if (this.left != null) this.left.parent(node);
if (this.right != null) this.right.parent(node);
if (this.parent != null) {
if (this.parentHasLeft) this.parent.right(node);
else this.parent.left(node);
}
return node;
}
}
private Integer value = null;
private BinaryNode parent = null;
private BinaryNode left = null;
private BinaryNode right = null;
private BinaryNode (Integer value) {
if (value < 0  value > 1)
throw new IllegalArgumentException(
"this is a binary tree... `value` can only be 0 or 1");
this.value = value;
}
public Integer value() {
return this.value;
}
public BinaryNode parent() {
return this.parent;
}
private void parent (BinaryNode parent) {
this.parent = parent;
}
public BinaryNode left() {
return this.left;
}
private void left (BinaryNode left) {
this.left = left;
}
public BinaryNode right() {
return this.right;
}
private void right (BinaryNode right) {
this.right = right;
}
...then we just need to add a few bits and pieces to get and set the node's unival status:
...
private Integer unival = null;
...
public Integer unival() {
return this.unival;
}
public void unival (Integer unival) {
this.unival = unival;
}
...
I've also added a nice (but not strictly necessary) method for printing an ASCII representation of the tree (values or unival statuses):
public void valueTree() { tree(false, 10, 10, "", false); }
public void univalTree() { tree(true, 10, 10, "", false); }
// some code here based on http://bit.ly/2HgFBRo
private void tree (boolean unival, int nLevelsUp, int nLevelsDown, String indent, boolean isTail) {
// start with any node on the tree
BinaryNode node = this;
// find eldest allowed node using nLevelsUp
for (int ii = 0; ii < nLevelsUp; ++ii) {
if (node.parent != null) {
node = node.parent;
++nLevelsDown;
} else {
nLevelsUp;
}
}
// get number of ancestors of this node
BinaryNode ptr = this;
int gen = 0;
while (ptr.parent() != null) {
++gen; ptr = ptr.parent();
}
Integer treeValue = unival ? node.unival : node.value;
String treeLabel = (treeValue == null ? "null" : treeValue.toString());
System.out.printf(" %3d %s %s%n", gen, indent, treeLabel);
int nChildren = (this.left == null ? 0 : 1) + (this.right == null ? 0 : 1);
BinaryNode lastChild = (nChildren > 1 ? this.right : this.left);
if (nLevelsDown > 0) {
if (nChildren > 1)
this.left.tree(unival, 0, nLevelsDown1, indent + (isTail ? " " : " "), false);
if (nChildren > 0)
lastChild.tree(unival, 0, nLevelsDown1, indent + (isTail ? " " : " "), true);
}
return;
}
So we can create nodes with 0, 1, or 2 children. Here's an example of how we could create a small binary tree and inspect its properties:
$ jshell cp target/0081.0SNAPSHOT.jar
 Welcome to JShell  Version 11.0.2
 For an introduction type: /help intro
jshell> import DCP.BinaryNode
jshell> (new BinaryNode.Builder(1)).build()
$2 ==> DCP.BinaryNode@210366b4
jshell> (new BinaryNode.Builder(0).parent($2)).build()
$3 ==> DCP.BinaryNode@2b2948e2
jshell> (new BinaryNode.Builder(1).parent($2)).build()
$4 ==> DCP.BinaryNode@57536d79
jshell> (new BinaryNode.Builder(1).parent($4)).build()
$5 ==> DCP.BinaryNode@5a8e6209
jshell> $2.valueTree()
0  1
1   0
1   1
2   1
Great! Now we just need to think about how we'd use these methods in the context of the problem. Let's take the procedure we defined above and replace actions with code snippets. Below, this
is a reference to the node on which we're currently focused, which changes throughout the process. When I say "refocus on X node" below, I mean that this
now refers to that node:
 (step 1)

if (this.unival == null)
go to (2) 
else parent = this.parent()

if (parent != null)
refocus onparent
and go back to the start of step (1) else return // we're finished!


 (step 2)

if (this.left == null && this.right == null) this.unival(this.value)
and go to (1b) 
else if (this.left != null ^ this.right != null)
move to that nonnull
child node, then go to the start of step (1). 
else

if (this.left != null)

if (this.right != null) this.unival(...)
to set this node's unival status based on left and right child node values then move to step (1b) 
else
refocus on the right node, then move back to the start of step (2).


else
refocus on the left node, then move back to the start of step (2).


Does this work? Here's a script I wrote to test this algorithm:
// Algo.java
import DCP.BinaryNode;
BinaryNode root = (new BinaryNode.Builder(1)).build();
BinaryNode nodeA = (new BinaryNode.Builder(0).parent(root)).build();
BinaryNode nodeB = (new BinaryNode.Builder(0).parent(nodeA)).build();
BinaryNode nodeC = (new BinaryNode.Builder(1).parent(nodeA)).build();
BinaryNode nodeD = (new BinaryNode.Builder(1).parent(root)).build();
BinaryNode nodeE = (new BinaryNode.Builder(1).parent(nodeD)).build();
BinaryNode nodeF = (new BinaryNode.Builder(1).parent(nodeD)).build();
root.valueTree();
BinaryNode thisnode = root;
while (true) {
// (1a)
if (thisnode.unival() == null) {
// (2a)
if (thisnode.left() == null && thisnode.right() == null) {
thisnode.unival(thisnode.value());
// (2b)
} else if (thisnode.left() != null ^ thisnode.right() != null) {
thisnode = (thisnode.left() == null ? thisnode.right() : thisnode.left());
// (2c)
} else {
if (thisnode.left() != null) {
if (thisnode.right() != null)
thisnode.unival((
thisnode.left().value() == thisnode.right().value()
? thisnode.left().value()
: 1
));
else thisnode = thisnode.right();
} else thisnode = thisnode.left();
}
// (1b)
} else {
BinaryNode parent = thisnode.parent();
// (1bi)
if (parent != null) thisnode = parent;
else break;
}
}
System.out.println();
root.univalTree();
...let's try it out in the jshell
:
$ jshell cp target/0081.0SNAPSHOT.jar
 Welcome to JShell  Version 11.0.2
 For an introduction type: /help intro
jshell> /open Algo.java
0  1
1   0
2    0
2    0
1   1
2   1
2   1
0  1
1   null
2    null
2    null
1   null
2   null
2   null
Not quite! Why did this happen?
The problem lies in step (2c) of the algorithm we defined, or, in the lines:
...
if (thisnode.left() != null) {
if (thisnode.right() != null)
thisnode.unival((
thisnode.left().value() == thisnode.right().value()
? thisnode.left().value()
: 1
));
...
This code checks that thisnode
has a nonnull
left and right child, but doesn't check whether the unival status of those nodes has been determined! The result is that we determine that the root node has two children, and then we set the root node's unival status, and then we quit, without updating the unival status of any other nodes.
This is a quick fix, all we have to do is change the above lines to:
...
if (thisnode.left() != null && thisnode.left().unival() != null) {
if (thisnode.right() != null && thisnode.right().unival() != null)
thisnode.unival((
thisnode.left().value() == thisnode.right().value()
? thisnode.left().value()
: 1
));
...
Let's try again!
jshell> /open Algo.java
0  1
1   0
2    0
2    1
1   1
2   1
2   1
0  1
1   1
2    0
2    1
1   1
2   1
2   1
Look's good! Let's try another tree:
jshell> /open Algo.java
0  1
1   0
2    0
2    1
1   1
2   1
2   0
0  1
1   1
2    0
2    1
1   1
2   1
2   0
It seems to be behaving properly. The final step is to count the number of nodes in the tree with unival statuses of 0
or 1
. We can do this by walking the tree and incrementing some global counter for every node that is nonnegative. Something like:
public int countUnivalSubtrees (BinaryNode node) {
boolean hasLeft = (node.left() != null);
boolean hasRight = (node.right() != null);
int sumLeft = hasLeft ? countUnivalSubtrees(node.left()) : 0;
int sumRight = hasRight ? countUnivalSubtrees(node.right()) : 0;
return((node.unival() >= 0 ? 1 : 0) + sumLeft + sumRight);
}
System.out.println("\nNumber of unival subtrees: " + countUnivalSubtrees(root));
This nearly works, but not quite. Can you see why?
Maybe an example will help:
jshell> /open Algo.java
0  0
1   0
2    0
2    1
1   0
2   0
2   1
0  0
1   1
2    0
2    1
1   1
2   0
2   1
Number of unival subtrees: 5
When a node has two children, and we check their unival status, we only check that they're equal, but not that they're valid:
thisnode.left().value() == thisnode.right().value()
? thisnode.left().value()
: 1
We need to check that they're valid (not equal to 1
):
thisnode.left().value() == thisnode.right().value() &&
thisnode.left().unival() >= 0
? thisnode.left().value()
: 1
Does this work?
jshell> /open Algo.java
0  0
1   1
2    1
2    1
1   1
2   1
2   1
0  1
1   1
2    1
2    1
1   1
2   1
2   1
Number of unival subtrees: 7
Almost! We just need to check that the unival status of the child node's subtrees is equal to the value of this node:
thisnode.left().value() == thisnode.right().value() &&
thisnode.left().unival() >= 0 &&
thisnode.left().value() == thisnode.value()
? thisnode.left().value()
: 1
Voila!
jshell> /open Algo.java
0  0
1   1
2    1
2    1
1   1
2   1
2   1
0  1
1   1
2    1
2    1
1   1
2   1
2   1
Number of unival subtrees: 6
Discussion
Finally, we can count the number of unival subtrees in a given tree. Let's try it one more time on the example tree given in the prompt:
jshell> /open Algo.java
0  0
1   0
1   1
2   0
2   1
3   1
3   1
0  1
1   0
1   1
2   0
2   1
3   1
3   1
Number of unival subtrees: 5
Looks good! And it gives the same value as in the prompt. In an earlier version of this writeup, I used a boolean
value for the unival
status, but quickly realised that there are more than two states (unival vs not unival, for instance). This necessitated a wider data type.
I also made some small oversights throughout the problem solution, at one point confusing value
and unival
. With the implementation of a binary tree plus actually solving the problem, this Daily Coding Problem was a bit of work, but eventually we arrived at a decent solution.
This solution could likely be optimised a bit, but that's a problem for another day.
All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.
Suggestions? Let me know in the comments.
If you enjoyed this post, please consider supporting my work by buying me a coffee!
Thanks for sharing your solution! Quite an interesting challenge.
I tried to solve it using Haskell since I'm currently learning the language, and after a few mistakes I ended up with the following code:
As you can see, it's pretty short, and for me it looks very readable.
Have a nice day!
If there's one thing Java ain't, it's succinct. Great solution!