Java Daily Coding Problem #008

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

Check if this.unival is null for this node.
1. If this.unival is null for this node, we haven't yet determined this node's subtree's unival status; go to (2).
2. If this.unival is not null for this node, attempt to move to this node's parent.
  1. If this node has a parent, refocus on the parent node, then go to the start of step (1).
  2. 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.
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.
1. If this node has 0 children, this subtree is unival. Set this.unival = this node's value and go to (1b).
2. 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).
3. 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 left node's unival status is null, refocus on that node, then go to step (1a).

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):

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, 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:

$ 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:

(step 1)
1. if (this.unival == null) go to (2)
2. else parent = this.parent()
  1. if (parent != null) refocus on parent and go back to the start of step (1)
  2. else return // we're finished!
(step 2)
1. if (this.left == null && this.right == null) this.unival(this.value) and go to (1b)
2. else if (this.left != null ^ this.right != null) move to that non-null child node, then go to the start of step (1).
3. 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/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:

...
      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:

...
      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 non-negative. 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!

Blog

Java Daily Coding Problem #008

Andrew (he/him)

Problem

Strategy

Code

Discussion

Join Our Newsletter. No Spam, Only the good stuff.

Related