Java Daily Coding Problem #008
Tags: java, challenge, beginners, devjournal
Published: 2019-10-02 17:23:13

[Daily Coding Problem](https://dailycodingproblem.com/) 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](https://en.wikipedia.org/wiki/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 0-unival, (3) determined and 1-unival, (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:

<ol type="1">
  <li>Check if <code>this.unival</code> is <code>null</code> for this node.
    <ol type="a">
      <li>If <code>this.unival</code> is <code>null</code> for this node, we haven't yet determined this node's subtree's unival status; go to (2).</li>
      <li>If <code>this.unival</code> is not <code>null</code> for this node, attempt to move to this node's parent.
        <ol type="i">
          <li>If this node has a parent, refocus on the parent node, then go to the start of step (1).</li>
          <li>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.</li>
        </ol>
      </li>
    </ol>
  </li>
  <li>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.
    <ol type="a">
      <li>If this node has 0 children, this subtree is unival. Set <code>this.unival = </code> this node's value and go to (1b).</li>
      <li>If this node has 1 child, check the unival status of that child
        <ul>
          <li>If the child's unival status is non-<code>null</code>, set the parent's unival status by examining its value and its child's value, then move to step (1b)</li>
          <li>If the child's unival status is <code>null</code>, refocus on that child node, then go to step (1a).</li>
        </ul>
      </li>
      <li>If this subtree's root node has 2 children, check the unival status of the left child node
        <ul>
          <li>If the left node's unival status is non-<code>null</code>, check the unival status of the right node
            <ul>
              <li>If the right node's unival status is non-<code>null</code>, we can determine its parent's unival status from the status of these two nodes. Set it, then move to step (1b).</li>
              <li>If the right node's unival status is <code>null</code>, refocus on that node, then go to step (1a).</li>
            </ul>
          </li>
          <li>If the left node's unival status is <code>null</code>, refocus on that node, then go to step (1a).</li>
        </ul>
      </li>
    </ol>
  </li>
</ol>

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 left-to-right, bottom-to-top 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](https://dzone.com/articles/design-patterns-the-builder-pattern)):

```java
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:

```java
...
  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):

```java
  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, nLevelsDown-1, indent + (isTail ? "    " : "|   "), false);

      if (nChildren > 0)
        lastChild.tree(unival, 0, nLevelsDown-1, 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:

```java
$ jshell -cp target/008-1.0-SNAPSHOT.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:

<ol type="1">
  <li>(step 1)
    <ol type="a">
      <li><code>if (this.unival == null)</code> go to (2)</li>
      <li><code>else parent = this.parent()</code>
        <ol type="i">
          <li><code>if (parent != null)</code> refocus on <code>parent</code> and go back to the start of step (1)</li>
          <li><code>else return // we're finished!</code></li>
        </ol>
      </li>
    </ol>
  </li>
  <li>(step 2)
    <ol type="a">
      <li><code>if (this.left == null && this.right == null) this.unival(this.value)</code> and go to (1b)</li>
      <li><code>else if (this.left != null ^ this.right != null)</code> move to that non-<code>null</code> child node, then go to the start of step (1).</li>
      <li><code>else</code>
        <ul>
          <li><code>if (this.left != null)</code>
            <ul>
              <li><code>if (this.right != null) this.unival(...)</code> to set this node's unival status based on left and right child node values then move to step (1b)</li>
              <li><code>else</code> refocus on the right node, then move back to the start of step (2).</li>
            </ul>
          </li>
          <li><code>else</code> refocus on the left node, then move back to the start of step (2).</li>
        </ul>
      </li>
    </ol>
  </li>
</ol>

Does this work? Here's a script I wrote to test this algorithm:

```java
// 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`:

```java
$ jshell -cp target/008-1.0-SNAPSHOT.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:

```java
...
      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 non-`null` 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:

```java
...
      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!

```java
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:

```java
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 non-negative. Something like:

```java
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:

```java
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:

```java
            thisnode.left().value() == thisnode.right().value()
              ? thisnode.left().value()
              : -1
```

We need to check that they're valid (not equal to `-1`):

```java
            thisnode.left().value() == thisnode.right().value() &&
            thisnode.left().unival() >= 0
              ? thisnode.left().value()
              : -1
```

Does this work?

```java
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:

```java
            thisnode.left().value() == thisnode.right().value() &&
            thisnode.left().unival() >= 0  &&
            thisnode.left().value() == thisnode.value()
              ? thisnode.left().value()
              : -1
```

Voila!

```java
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:

```java
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](https://stackoverflow.com/q/310974/2925434), but that's a problem for another day.

---

All the code for my Daily Coding Problems solutions is available at [github.com/awwsmm/daily](https://github.com/awwsmm/daily).

Suggestions? Let me know in the comments.

If you enjoyed this post, please consider supporting my work by <a href='https://ko-fi.com/Z8Z811E9B'>buying me a coffee</a>!