How to deserialize a JSON object to a binary tree?

[Frank Dai]

From the previous question How to deserialize a JSON array to a singly linked list , I learned how to deserialize a JSON array to a singly linked list.

Now I want to deserialize a JSON object to a binary tree in Java.

The definition of the binary tree node is as the following:

public class BinaryTreeNode<E> {
    public E value;
    public BinaryTreeNode left;
    public BinaryTreeNode right;
    public BinaryTreeNode(final E value) {
        this.value = value;
    }
}

How to deserialize a JSON string such as:

{
  "value": 2,
  "left": {
    "value": 1,
    "left": null,
    "right": null
  },
  "right": {
    "value": 10,
    "left": {
      "value": 5,
      "left": null,
      "right": null
    },
    "right": null
  }
}

to a binary tree?

  2 
 / \ 
1   10 
   / 
  5

Here is the unit test code:

@Test public void binaryTreeNodeTest() throws IOException {
    ObjectMapper objectMapper = new ObjectMapper();

    final ArrayList<Integer> intArray = objectMapper.readValue("[1,2,3,4,5]",
        new TypeReference<ArrayList<Integer>>() {});
    System.out.println(intArray);

    /* How to achieve this?
         2
        / \
       1   10
          /
         5
     {
       "value": 2,
       "left": {
        "value": 1,
        "left": null,
        "right": null
      },
      "right": {
        "value": 10,
        "left": {
          "value": 5,
          "left": null,
          "right": null
        },
        "right": null
      }
    }
    */
    final String jsonStr = "{\n"
        + "  \"value\": 2,\n"
        + "  \"left\": {\n"
        + "    \"value\": 1,\n"
        + "    \"left\": null,\n"
        + "    \"right\": null\n"
        + "  },\n" + "  \"right\": {\n"
        + "    \"value\": 10,\n"
        + "    \"left\": {\n"
        + "      \"value\": 5,\n"
        + "      \"left\": null,\n"
        + "      \"right\": null\n"
        + "    },\n"
        + "    \"right\": null\n"
        + "  }\n"
        + "}";
    System.out.println(jsonStr);
    final BinaryTreeNode<Integer> intTree = objectMapper.readValue(jsonStr,
        new TypeReference<BinaryTreeNode<Integer>>() {});
    System.out.println(intTree);
}

In other word, I want the BinaryTreeNode to be a first-class citizen the same as ArrayList, which can be used in all kinds of combinations, such as HashSet<BinaryTreeNode<Integer>>, BinaryTreeNode<HashMap<String, Integer>>, etc.

[Tatu Saloranta]

If you defined subtype like:

   public class BinaryIntegerTree extends BinaryTreeNode<Integer> { }

it should work as you show. But whether it works via generic parameterization I don't know.

What happens when you run the test?

-+ Tatu +-

--
You received this message because you are subscribed to the Google Groups "jackson-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jackson-user...@googlegroups.com.
To post to this group, send email to jackso...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Frank Dai]

com.fasterxml.jackson.databind.JsonMappingException: No suitable constructor found for type [simple type, class org.algorithmhub.customized_collection.BinaryTreeNodeTest$BinaryTreeNode<java.lang.Integer>]: can not instantiate from JSON object (missing default constructor or creator, or perhaps need to add/enable type information?)
 at [Source: {
  "value": 2,
  "left": {
    "value": 1,
    "left": null,
    "right": null
  },
  "right": {
    "value": 10,
    "left": {
      "value": 5,
      "left": null,
      "right": null
    },
    "right": null
  }
}; line: 2, column: 3]
    at com.fasterxml.jackson.databind.JsonMappingException.from(JsonMappingException.java:148)
    at com.fasterxml.jackson.databind.deser.BeanDeserializerBase.deserializeFromObjectUsingNonDefault(BeanDeserializerBase.java:1080)
    at com.fasterxml.jackson.databind.deser.BeanDeserializer.deserializeFromObject(BeanDeserializer.java:295)
    at com.fasterxml.jackson.databind.deser.BeanDeserializer.deserialize(BeanDeserializer.java:142)
    at com.fasterxml.jackson.databind.ObjectMapper._readMapAndClose(ObjectMapper.java:3562)
    at com.fasterxml.jackson.databind.ObjectMapper.readValue(ObjectMapper.java:2597)
    at org.algorithmhub.customized_collection.BinaryTreeNodeTest.binaryTreeNodeTest(BinaryTreeNodeTest.java:71)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
    at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
    at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
    at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
    at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
    at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:78)
    at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:212)
    at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:68)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:140)

I guess I need to implement the java.util.Collection interface, but I have no idea how to do that.

[Tatu Saloranta]

No, you are not binding JSON Array. I think you need to try to think in terms of very simple mapping of JSON values (Objects, Arrays, scalars) to matching Java constructs (POJOs/Maps, arrays/Collections, primitives/wrappers).

In this specific case, however, the problem comes from the fact that you have neither zero-argument constructor, nor constructor marked with @JsonCreator.

You can do either, but given existing definition you probably want to use this:

  @JsonCreator

  public BinaryTreeNode(@JsonProperty("value") final E value) {

    this.value = value;
  }

which will tell Jackson that it should use this constructor, and that the first argument should be for logical property "value". The reason why annotation is needed here is that JVM/JDK do not retain argument name information in bytecode, at least not before Java 8 which adds this capability.

Hope this helps,

-+ Tatu +-

[Frank Dai]

It works! Thank you very much! @Tatu

Wow, Jackson is so powerful and yet so simple!

import com.fasterxml.jackson.annotation.JsonCreator;
import com.fasterxml.jackson.annotation.JsonProperty;
import com.fasterxml.jackson.core.type.TypeReference;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.junit.Test;

import java.io.IOException;
import java.util.ArrayList;


public class BinaryTreeNodeTest {
    public static class BinaryTreeNode<E> {
        public E value;
        public BinaryTreeNode left;
        public BinaryTreeNode right;

        @JsonCreator
        public BinaryTreeNode(@JsonProperty("value") final E value) {
            this.value = value;
        }
    }
    @Test public void binaryTreeNodeTest() throws IOException {
        ObjectMapper objectMapper = new ObjectMapper();

        final ArrayList<Integer> intArray = objectMapper.readValue("[1,2,3,4,5]",
            new TypeReference<ArrayList<Integer>>() {});
        System.out.println(intArray);

        /* How to achieve this?
             2
            / \
           1   10
              /
             5
         {
           "value": 2,
           "left": {
            "value": 1,
            "left": null,
            "right": null
          },
          "right": {
            "value": 10,
            "left": {
              "value": 5,
              "left": null,
              "right": null
            },
            "right": null
          }
        }
        */
        final String jsonStr = "{\n"
            + "  \"value\": 2,\n"
            + "  \"left\": {\n"
            + "    \"value\": 1,\n"
            + "    \"left\": null,\n"
            + "    \"right\": null\n"
            + "  },\n" + "  \"right\": {\n"
            + "    \"value\": 10,\n"
            + "    \"left\": {\n"
            + "      \"value\": 5,\n"
            + "      \"left\": null,\n"
            + "      \"right\": null\n"
            + "    },\n"
            + "    \"right\": null\n"
            + "  }\n"
            + "}";
        System.out.println(jsonStr);
        final BinaryTreeNode<Integer> intTree = objectMapper.readValue(jsonStr,
            new TypeReference<BinaryTreeNode<Integer>>() {});
        System.out.println(intTree);
    }
}

[Tatu Saloranta]

Glad to hear it works!

-+ Tatu +-

[Frank Dai]

To summarize, I wrote two blogs, 

Deserialize a JSON Array to a Singly Linked List

Deserialize a JSON String to a Binary Tree

[Tatu Saloranta]

Thank you for sharing these!

-+ Tatu +-

On Mon, Jun 22, 2015 at 3:10 AM, Frank Dai <soulm...@gmail.com> wrote:

To summarize, I write two blogs, 

Deserialize a JSON Array to a Singly Linked List

Deserialize a JSON String to a Binary Tree