Index: uspace/app/bithenge/blob.c
===================================================================
--- uspace/app/bithenge/blob.c	(revision 0d1a8fd13c2080836b202a79f4c1de55f2044547)
+++ uspace/app/bithenge/blob.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
@@ -59,4 +59,5 @@
 
 	blob->base.type = BITHENGE_NODE_BLOB;
+	blob->base.refs = 1;
 	blob->base.blob_ops = ops;
 	return EOK;
Index: uspace/app/bithenge/script.c
===================================================================
--- uspace/app/bithenge/script.c	(revision 0d1a8fd13c2080836b202a79f4c1de55f2044547)
+++ uspace/app/bithenge/script.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
@@ -328,4 +328,5 @@
 		free(entry->name);
 		bithenge_transform_dec_ref(entry->transform);
+		free(entry);
 		entry = next;
 	}
Index: uspace/app/bithenge/test.c
===================================================================
--- uspace/app/bithenge/test.c	(revision 0d1a8fd13c2080836b202a79f4c1de55f2044547)
+++ uspace/app/bithenge/test.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
@@ -67,5 +67,5 @@
 		bithenge_print_node(BITHENGE_PRINT_JSON, node);
 		printf("\n");
-		bithenge_node_destroy(node);
+		bithenge_node_dec_ref(node);
 	} else {
 		bithenge_transform_t *transform;
@@ -89,5 +89,5 @@
 		}
 
-		bithenge_node_destroy(node);
+		bithenge_node_dec_ref(node);
 		bithenge_transform_dec_ref(transform);
 
@@ -97,4 +97,5 @@
 			return 1;
 		}
+		bithenge_node_dec_ref(node2);
 		printf("\n");
 	}
Index: uspace/app/bithenge/transform.h
===================================================================
--- uspace/app/bithenge/transform.h	(revision 0d1a8fd13c2080836b202a79f4c1de55f2044547)
+++ uspace/app/bithenge/transform.h	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
@@ -104,5 +104,5 @@
 }
 
-/** Decrement a transform's reference count.
+/** Decrement a transform's reference count and free it if appropriate.
  * @param xform The transform to dereference, or NULL.
  * @return EOK on success or an error code from errno.h. */
Index: uspace/app/bithenge/tree.c
===================================================================
--- uspace/app/bithenge/tree.c	(revision 0d1a8fd13c2080836b202a79f4c1de55f2044547)
+++ uspace/app/bithenge/tree.c	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
@@ -48,9 +48,5 @@
 }
 
-/** Destroy a node.
- * @memberof bithenge_node_t
- * @param node The node to destroy.
- * @return EOK on success or an error code from errno.h. */
-int bithenge_node_destroy(bithenge_node_t *node)
+static int node_destroy(bithenge_node_t *node)
 {
 	switch (bithenge_node_type(node)) {
@@ -72,4 +68,17 @@
 }
 
+/** Decrement a node's reference count and free it if appropriate.
+ * @memberof bithenge_node_t
+ * @param node The node to dereference, or NULL.
+ * @return EOK on success or an error code from errno.h. */
+int bithenge_node_dec_ref(bithenge_node_t *node)
+{
+	if (!node)
+		return EOK;
+	if (--node->refs == 0)
+		return node_destroy(node);
+	return EOK;
+}
+
 typedef struct
 {
@@ -83,4 +92,9 @@
 {
 	return (simple_internal_node_t *)node;
+}
+
+static bithenge_node_t *simple_as_node(simple_internal_node_t *node)
+{
+	return &node->base;
 }
 
@@ -102,9 +116,6 @@
 	int rc;
 	simple_internal_node_t *node = node_as_simple(base);
-	for (bithenge_int_t i = 0; i < node->len; i++) {
-		rc = bithenge_node_destroy(node->nodes[2*i+0]);
-		if (rc != EOK)
-			return rc;
-		rc = bithenge_node_destroy(node->nodes[2*i+1]);
+	for (bithenge_int_t i = 0; i < 2 * node->len; i++) {
+		rc = bithenge_node_dec_ref(node->nodes[i]);
 		if (rc != EOK)
 			return rc;
@@ -121,12 +132,7 @@
 };
 
-static bithenge_node_t *simple_internal_as_node(simple_internal_node_t *node)
-{
-	return &node->base;
-}
-
-/** Create an internal node from a set of keys and values. The node must be
- * freed with @a bithenge_node_t::bithenge_node_destroy after it is used, which
- * will also destroy all the key and value nodes.
+/** Create an internal node from a set of keys and values. This function takes
+ * ownership of a reference to the key and value nodes, and optionally the
+ * array @a nodes.
  * @memberof bithenge_node_t
  * @param[out] out Stores the created internal node.
@@ -135,5 +141,5 @@
  * @param len The number of key-value pairs in the node array.
  * @param needs_free If true, when the internal node is destroyed it will free
- * the nodes array as well as destroying each node inside it.
+ * the nodes array rather than just dereferencing each node inside it.
  * @return EOK on success or an error code from errno.h. */
 int bithenge_new_simple_internal_node(bithenge_node_t **out,
@@ -142,20 +148,25 @@
 	assert(out);
 	simple_internal_node_t *node = malloc(sizeof(*node));
-	if (!node)
+	if (!node) {
+		for (bithenge_int_t i = 0; i < 2 * len; i++)
+			bithenge_node_dec_ref(nodes[i]);
+		if (needs_free)
+			free(nodes);
 		return ENOMEM;
+	}
 	node->base.type = BITHENGE_NODE_INTERNAL;
+	node->base.refs = 1;
 	node->base.internal_ops = &simple_internal_node_ops;
 	node->nodes = nodes;
 	node->len = len;
 	node->needs_free = needs_free;
-	*out = simple_internal_as_node(node);
-	return EOK;
-}
-
-static bithenge_node_t false_node = { BITHENGE_NODE_BOOLEAN, .boolean_value = false };
-static bithenge_node_t true_node = { BITHENGE_NODE_BOOLEAN, .boolean_value = true };
-
-/** Create a boolean node. The node must be freed with @a
- * bithenge_node_t::bithenge_node_destroy after it is used.
+	*out = simple_as_node(node);
+	return EOK;
+}
+
+static bithenge_node_t false_node = { BITHENGE_NODE_BOOLEAN, 1, .boolean_value = false };
+static bithenge_node_t true_node = { BITHENGE_NODE_BOOLEAN, 1, .boolean_value = true };
+
+/** Create a boolean node.
  * @memberof bithenge_node_t
  * @param[out] out Stores the created boolean node.
@@ -166,9 +177,9 @@
 	assert(out);
 	*out = value ? &true_node : &false_node;
-	return EOK;
-}
-
-/** Create an integer node. The node must be freed with @a
- * bithenge_node_t::bithenge_node_destroy after it is used.
+	(*out)->refs++;
+	return EOK;
+}
+
+/** Create an integer node.
  * @memberof bithenge_node_t
  * @param[out] out Stores the created integer node.
@@ -182,4 +193,5 @@
 		return ENOMEM;
 	node->type = BITHENGE_NODE_INTEGER;
+	node->refs = 1;
 	node->integer_value = value;
 	*out = node;
@@ -187,6 +199,5 @@
 }
 
-/** Create a string node. The node must be freed with @a
- * bithenge_node_t::bithenge_node_destroy after it is used.
+/** Create a string node.
  * @memberof bithenge_node_t
  * @param[out] out Stores the created string node.
@@ -202,4 +213,5 @@
 		return ENOMEM;
 	node->type = BITHENGE_NODE_STRING;
+	node->refs = 1;
 	node->string_value.ptr = value;
 	node->string_value.needs_free = needs_free;
Index: uspace/app/bithenge/tree.h
===================================================================
--- uspace/app/bithenge/tree.h	(revision 0d1a8fd13c2080836b202a79f4c1de55f2044547)
+++ uspace/app/bithenge/tree.h	(revision f2da0bb463ab6b12422771a11818973383ea2d98)
@@ -68,4 +68,5 @@
 	/** @privatesection */
 	bithenge_node_type_t type;
+	unsigned int refs;
 	union {
 		const struct bithenge_internal_node_ops_t *internal_ops;
@@ -104,4 +105,17 @@
 	return node->type;
 }
+
+/** Increment a node's reference count.
+ * @memberof bithenge_node_t
+ * @param node The node to reference.
+ * @return EOK on success or an error code from errno.h. */
+static inline int bithenge_node_inc_ref(bithenge_node_t *node)
+{
+	assert(node);
+	node->refs++;
+	return EOK;
+}
+
+int bithenge_node_dec_ref(bithenge_node_t *node);
 
 /** Iterate over a node's children.
@@ -152,5 +166,4 @@
 int bithenge_new_integer_node(bithenge_node_t **, bithenge_int_t);
 int bithenge_new_string_node(bithenge_node_t **, const char *, bool);
-int bithenge_node_destroy(bithenge_node_t *);
 bool bithenge_node_equal(bithenge_node_t *, bithenge_node_t *);