Repository: yorkie-team/yorkie
Pull request #566 (2023-06-28 12:54:45)

Apply garbage collection for tree
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:
- Apply garbage collection for tree
- Fix some issues
  - miscalculation in `pathToTreePos`
  - null point exception when `Node.Parent` is `nil`

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Fixes #

**Special notes for your reviewer**:

**Does this PR introduce a user-facing change?**:
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".
-->
```release-note

```

**Additional documentation**:

<!--
This section can be blank if this pull request does not require a release note.

Please use the following format for linking documentation:
- [Usage]: <link>
- [Other doc]: <link>
-->
```docs

```

**Checklist**:
- [x] Added relevant tests or not required
- [x] Didn't break anything


CLAassistant: [![CLA assistant check](https://cla-assistant.io/pull/badge/not_signed)](https://cla-assistant.io/yorkie-team/yorkie?pullRequest=566) <br/>Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our [Contributor License Agreement](https://cla-assistant.io/yorkie-team/yorkie?pullRequest=566) before we can accept your contribution.<br/><hr/>**jooho-jang** seems not to be a GitHub user. You need a GitHub account to be able to sign the CLA. If you have already a GitHub account, please [add the email address used for this commit to your account](https://help.github.com/articles/why-are-my-commits-linked-to-the-wrong-user/#commits-are-not-linked-to-any-user).<br/><sub>You have signed the CLA already but the status is still pending? Let us [recheck](https://cla-assistant.io/check/yorkie-team/yorkie?pullRequest=566) it.</sub>
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) Report
> Merging [#566](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (2885888) into [main](https://app.codecov.io/gh/yorkie-team/yorkie/commit/7eee5514f1fc7da5f1e7424580362d0fa01ecec7?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (7eee551) will **decrease** coverage by `0.33%`.
> The diff coverage is `26.66%`.

```diff
@@            Coverage Diff             @@
##             main     #566      +/-   ##
==========================================
- Coverage   52.27%   51.94%   -0.33%     
==========================================
  Files          67       67              
  Lines        6797     6847      +50     
==========================================
+ Hits         3553     3557       +4     
- Misses       2806     2851      +45     
- Partials      438      439       +1     
```


| [Impacted Files](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) | Coverage Δ | |
|---|---|---|
| [pkg/document/change/context.go](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2NoYW5nZS9jb250ZXh0Lmdv) | `0.00% <0.00%> (ø)` | |
| [pkg/document/crdt/rga\_tree\_split.go](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2NyZHQvcmdhX3RyZWVfc3BsaXQuZ28=) | `69.60% <ø> (ø)` | |
| [pkg/index/tree.go](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2luZGV4L3RyZWUuZ28=) | `50.17% <0.00%> (-3.01%)` | :arrow_down: |
| [pkg/document/crdt/tree.go](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2NyZHQvdHJlZS5nbw==) | `65.38% <23.52%> (-6.91%)` | :arrow_down: |
| [pkg/document/crdt/root.go](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2NyZHQvcm9vdC5nbw==) | `75.86% <100.00%> (ø)` | |
| [pkg/document/crdt/text.go](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2NyZHQvdGV4dC5nbw==) | `57.84% <100.00%> (ø)` | |

... and [1 file with indirect coverage changes](https://app.codecov.io/gh/yorkie-team/yorkie/pull/566/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team)



Patch:
diff --git a/pkg/document/change/context.go b/pkg/document/change/context.go
index 560f9e16..931d7859 100644
--- a/pkg/document/change/context.go
+++ b/pkg/document/change/context.go
@@ -78,9 +78,9 @@ func (c *Context) RegisterRemovedElementPair(parent crdt.Container, deleted crdt
 	c.root.RegisterRemovedElementPair(parent, deleted)
 }
 
-// RegisterTextElementWithGarbage register the given text element with garbage to hash table.
-func (c *Context) RegisterTextElementWithGarbage(textType crdt.TextElement) {
-	c.root.RegisterTextElementWithGarbage(textType)
+// RegisterElementHasRemovedNodes register the given text element with garbage to hash table.
+func (c *Context) RegisterElementHasRemovedNodes(element crdt.GCElement) {
+	c.root.RegisterElementHasRemovedNodes(element)
 }
 
 // LastTimeTicket returns the last time ticket issued by this context.
diff --git a/pkg/document/crdt/element.go b/pkg/document/crdt/element.go
index c2f155b1..c7c7ee22 100644
--- a/pkg/document/crdt/element.go
+++ b/pkg/document/crdt/element.go
@@ -34,11 +34,11 @@ type Container interface {
 	DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) Element
 }
 
-// TextElement represents Text.
-type TextElement interface {
+// GCElement represents Element which has GC.
+type GCElement interface {
 	Element
 	removedNodesLen() int
-	purgeTextNodesWithGarbage(ticket *time.Ticket) int
+	purgeRemovedNodesBefore(ticket *time.Ticket) int
 }
 
 // Element represents JSON element.
diff --git a/pkg/document/crdt/rga_tree_split.go b/pkg/document/crdt/rga_tree_split.go
index a224e08f..5c4b9ee0 100644
--- a/pkg/document/crdt/rga_tree_split.go
+++ b/pkg/document/crdt/rga_tree_split.go
@@ -631,8 +631,8 @@ func (s *RGATreeSplit[V]) removedNodesLen() int {
 	return len(s.removedNodeMap)
 }
 
-// purgeTextNodesWithGarbage physically purges nodes that have been removed.
-func (s *RGATreeSplit[V]) purgeTextNodesWithGarbage(ticket *time.Ticket) int {
+// purgeRemovedNodesBefore physically purges nodes that have been removed.
+func (s *RGATreeSplit[V]) purgeRemovedNodesBefore(ticket *time.Ticket) int {
 	count := 0
 	for _, node := range s.removedNodeMap {
 		if node.removedAt != nil && ticket.Compare(node.removedAt) >= 0 {
diff --git a/pkg/document/crdt/root.go b/pkg/document/crdt/root.go
index 7aa7a2dd..9b4c860c 100644
--- a/pkg/document/crdt/root.go
+++ b/pkg/document/crdt/root.go
@@ -39,7 +39,7 @@ type Root struct {
 	object                               *Object
 	elementMapByCreatedAt                map[string]Element
 	removedElementPairMapByCreatedAt     map[string]ElementPair
-	textElementWithGarbageMapByCreatedAt map[string]TextElement
+	elementHasRemovedNodesSetByCreatedAt map[string]GCElement
 }
 
 // NewRoot creates a new instance of Root.
@@ -47,7 +47,7 @@ func NewRoot(root *Object) *Root {
 	r := &Root{
 		elementMapByCreatedAt:                make(map[string]Element),
 		removedElementPairMapByCreatedAt:     make(map[string]ElementPair),
-		textElementWithGarbageMapByCreatedAt: make(map[string]TextElement),
+		elementHasRemovedNodesSetByCreatedAt: make(map[string]GCElement),
 	}
 
 	r.object = root
@@ -95,9 +95,9 @@ func (r *Root) RegisterRemovedElementPair(parent Container, elem Element) {
 	}
 }
 
-// RegisterTextElementWithGarbage register the given text element with garbage to hash table.
-func (r *Root) RegisterTextElementWithGarbage(textType TextElement) {
-	r.textElementWithGarbageMapByCreatedAt[textType.CreatedAt().Key()] = textType
+// RegisterElementHasRemovedNodes register the given element with garbage to hash table.
+func (r *Root) RegisterElementHasRemovedNodes(element GCElement) {
+	r.elementHasRemovedNodesSetByCreatedAt[element.CreatedAt().Key()] = element
 }
 
 // DeepCopy copies itself deeply.
@@ -120,12 +120,12 @@ func (r *Root) GarbageCollect(ticket *time.Ticket) int {
 		}
 	}
 
-	for _, text := range r.textElementWithGarbageMapByCreatedAt {
-		purgedTextNodes := text.purgeTextNodesWithGarbage(ticket)
-		if purgedTextNodes > 0 {
-			delete(r.textElementWithGarbageMapByCreatedAt, text.CreatedAt().Key())
+	for _, node := range r.elementHasRemovedNodesSetByCreatedAt {
+		purgedNodes := node.purgeRemovedNodesBefore(ticket)
+		if purgedNodes > 0 {
+			delete(r.elementHasRemovedNodesSetByCreatedAt, node.CreatedAt().Key())
 		}
-		count += purgedTextNodes
+		count += purgedNodes
 	}
 
 	return count
@@ -157,8 +157,8 @@ func (r *Root) GarbageLen() int {
 		}
 	}
 
-	for _, text := range r.textElementWithGarbageMapByCreatedAt {
-		count += text.removedNodesLen()
+	for _, element := range r.elementHasRemovedNodesSetByCreatedAt {
+		count += element.removedNodesLen()
 	}
 
 	return count
diff --git a/pkg/document/crdt/text.go b/pkg/document/crdt/text.go
index 7a42bc0e..c6378c31 100644
--- a/pkg/document/crdt/text.go
+++ b/pkg/document/crdt/text.go
@@ -309,7 +309,7 @@ func (t *Text) removedNodesLen() int {
 	return t.rgaTreeSplit.removedNodesLen()
 }
 
-// purgeTextNodesWithGarbage physically purges nodes that have been removed.
-func (t *Text) purgeTextNodesWithGarbage(ticket *time.Ticket) int {
-	return t.rgaTreeSplit.purgeTextNodesWithGarbage(ticket)
+// purgeRemovedNodesBefore physically purges nodes that have been removed.
+func (t *Text) purgeRemovedNodesBefore(ticket *time.Ticket) int {
+	return t.rgaTreeSplit.purgeRemovedNodesBefore(ticket)
 }
diff --git a/pkg/document/crdt/tree.go b/pkg/document/crdt/tree.go
index 5a76232e..6280d5a3 100644
--- a/pkg/document/crdt/tree.go
+++ b/pkg/document/crdt/tree.go
@@ -19,6 +19,7 @@ package crdt
 import (
 	"errors"
 	"fmt"
+	"strconv"
 	"strings"
 	"unicode/utf16"
 
@@ -248,9 +249,10 @@ func (n *TreeNode) DeepCopy() *TreeNode {
 // Tree represents the tree of CRDT. It has doubly linked list structure and
 // index tree structure.
 type Tree struct {
-	DummyHead    *TreeNode
-	IndexTree    *index.Tree[*TreeNode]
-	NodeMapByPos *llrb.Tree[*TreePos, *TreeNode]
+	DummyHead      *TreeNode
+	IndexTree      *index.Tree[*TreeNode]
+	NodeMapByPos   *llrb.Tree[*TreePos, *TreeNode]
+	removedNodeMap map[string]*TreeNode
 
 	createdAt *time.Ticket
 	movedAt   *time.Ticket
@@ -260,10 +262,11 @@ type Tree struct {
 // NewTree creates a new instance of Tree.
 func NewTree(root *TreeNode, createdAt *time.Ticket) *Tree {
 	tree := &Tree{
-		DummyHead:    NewTreeNode(DummyTreePos, DummyHeadType, nil),
-		IndexTree:    index.NewTree[*TreeNode](root.IndexTreeNode),
-		NodeMapByPos: llrb.NewTree[*TreePos, *TreeNode](),
-		createdAt:    createdAt,
+		DummyHead:      NewTreeNode(DummyTreePos, DummyHeadType, nil),
+		IndexTree:      index.NewTree[*TreeNode](root.IndexTreeNode),
+		NodeMapByPos:   llrb.NewTree[*TreePos, *TreeNode](),
+		removedNodeMap: make(map[string]*TreeNode),
+		createdAt:      createdAt,
 	}
 
 	previous := tree.DummyHead
@@ -282,6 +285,64 @@ func (t *Tree) Marshal() string {
 	return builder.String()
 }
 
+// removedNodesLen returns the length of removed nodes.
+func (t *Tree) removedNodesLen() int {
+	return len(t.removedNodeMap)
+}
+
+// purgeRemovedNodesBefore physically purges nodes that have been removed.
+func (t *Tree) purgeRemovedNodesBefore(ticket *time.Ticket) int {
+	count := 0
+	nodesToBeRemoved := make(map[*TreeNode]bool)
+
+	for _, node := range t.removedNodeMap {
+		if node.RemovedAt != nil && ticket.Compare(node.RemovedAt) >= 0 {
+			count++
+			nodesToBeRemoved[node] = true
+		}
+	}
+
+	index.TraverseAll(t.IndexTree, func(node *index.Node[*TreeNode], depth int) {
+		_, ok := nodesToBeRemoved[node.Value]
+
+		if ok {
+			parent := node.Parent
+
+			if parent == nil {
+				count--
+				delete(nodesToBeRemoved, node.Value)
+
+				return
+			}
+
+			parent.RemoveChild(node)
+		}
+	})
+
+	for node := range nodesToBeRemoved {
+		t.NodeMapByPos.Remove(node.Pos)
+		t.Purge(node)
+		delete(t.removedNodeMap, node.Pos.CreatedAt.StructureAsString()+":"+strconv.Itoa(node.Pos.Offset))
+	}
+
+	return count
+}
+
+// Purge physically purges the given node.
+func (t *Tree) Purge(node *TreeNode) {
+	if node.Prev != nil {
+		node.Prev.Next = node.Next
+	}
+
+	if node.Next != nil {
+		node.Next.Prev = node.Prev
+	}
+
+	node.Prev = nil
+	node.Next = nil
+	node.InsPrev = nil
+}
+
 // marshal returns the JSON encoding of this Tree.
 func marshal(builder *strings.Builder, node *TreeNode) {
 	if node.IsText() {
@@ -411,6 +472,10 @@ func (t *Tree) Edit(from, to *TreePos, content *TreeNode, editedAt *time.Ticket)
 		isRangeOnSameBranch := toPos.Node.IsAncestorOf(fromPos.Node)
 		for _, node := range toBeRemoveds {
 			node.remove(editedAt)
+
+			if node.IsRemoved() {
+				t.removedNodeMap[node.Pos.CreatedAt.StructureAsString()+":"+strconv.Itoa(node.Pos.Offset)] = node
+			}
 		}
 
 		// move the alive children of the removed block node
@@ -433,7 +498,7 @@ func (t *Tree) Edit(from, to *TreePos, content *TreeNode, editedAt *time.Ticket)
 				}
 			}
 		} else {
-			if fromPos.Node.Parent.Value.IsRemoved() {
+			if fromPos.Node.Parent != nil && fromPos.Node.Parent.Value.IsRemoved() {
 				toPos.Node.Parent.Prepend(fromPos.Node.Parent.Children()...)
 			}
 		}
diff --git a/pkg/document/json/text.go b/pkg/document/json/text.go
index 333a775c..7129ba82 100644
--- a/pkg/document/json/text.go
+++ b/pkg/document/json/text.go
@@ -86,7 +86,7 @@ func (p *Text) Edit(from, to int, content string, attributes ...map[string]strin
 		ticket,
 	))
 	if !fromPos.Equal(toPos) {
-		p.context.RegisterTextElementWithGarbage(p)
+		p.context.RegisterElementHasRemovedNodes(p)
 	}
 
 	return p
diff --git a/pkg/document/json/tree.go b/pkg/document/json/tree.go
index 082b17d1..96ecc206 100644
--- a/pkg/document/json/tree.go
+++ b/pkg/document/json/tree.go
@@ -102,6 +102,10 @@ func (t *Tree) Edit(fromIdx, toIdx int, content *TreeNode) bool {
 		ticket,
 	))
 
+	if fromPos.CreatedAt.Compare(toPos.CreatedAt) != 0 || fromPos.Offset != toPos.Offset {
+		t.context.RegisterElementHasRemovedNodes(t.Tree)
+	}
+
 	return true
 }
 
@@ -147,6 +151,10 @@ func (t *Tree) EditByPath(fromPath []int, toPath []int, content *TreeNode) bool
 		ticket,
 	))
 
+	if fromPos.CreatedAt.Compare(toPos.CreatedAt) != 0 || fromPos.Offset != toPos.Offset {
+		t.context.RegisterElementHasRemovedNodes(t.Tree)
+	}
+
 	return true
 }
 
diff --git a/pkg/document/operations/edit.go b/pkg/document/operations/edit.go
index b1fd50ba..adafeec4 100644
--- a/pkg/document/operations/edit.go
+++ b/pkg/document/operations/edit.go
@@ -80,7 +80,7 @@ func (e *Edit) Execute(root *crdt.Root) error {
 			return err
 		}
 		if !e.from.Equal(e.to) {
-			root.RegisterTextElementWithGarbage(obj)
+			root.RegisterElementHasRemovedNodes(obj)
 		}
 	default:
 		return ErrNotApplicableDataType
diff --git a/pkg/document/operations/tree_edit.go b/pkg/document/operations/tree_edit.go
index 7368e8b6..d9d38af8 100644
--- a/pkg/document/operations/tree_edit.go
+++ b/pkg/document/operations/tree_edit.go
@@ -68,6 +68,10 @@ func (e *TreeEdit) Execute(root *crdt.Root) error {
 			content = e.Content().DeepCopy()
 		}
 		obj.Edit(e.from, e.to, content, e.executedAt)
+
+		if e.from.CreatedAt.Compare(e.to.CreatedAt) != 0 || e.from.Offset != e.to.Offset {
+			root.RegisterElementHasRemovedNodes(obj)
+		}
 	default:
 		return ErrNotApplicableDataType
 	}
diff --git a/pkg/index/tree.go b/pkg/index/tree.go
index 05fb012b..c482a499 100644
--- a/pkg/index/tree.go
+++ b/pkg/index/tree.go
@@ -78,17 +78,29 @@ const (
 
 // TraverseNode traverses the tree with the given callback.
 func TraverseNode[V Value](node *Node[V], callback func(node *Node[V], depth int)) {
-	postOrderTraversal(node, callback, 0)
+	postorderTraversal(node, callback, 0)
 }
 
-// postOrderTraversal traverses the tree with postorder traversal.
-func postOrderTraversal[V Value](node *Node[V], callback func(node *Node[V], depth int), depth int) {
+// postorderTraversal traverses the tree with postorder traversal.
+func postorderTraversal[V Value](node *Node[V], callback func(node *Node[V], depth int), depth int) {
 	if node == nil {
 		return
 	}
 
 	for _, child := range node.Children() {
-		postOrderTraversal(child, callback, depth+1)
+		postorderTraversal(child, callback, depth+1)
+	}
+	callback(node, depth)
+}
+
+// postorderTraversalAll traverses the whole tree (include tombstones) with postorder traversal.
+func postorderTraversalAll[V Value](node *Node[V], callback func(node *Node[V], depth int), depth int) {
+	if node == nil {
+		return
+	}
+
+	for _, child := range node.children {
+		postorderTraversalAll(child, callback, depth+1)
 	}
 	callback(node, depth)
 }
@@ -157,7 +169,12 @@ func ToXML[V Value](node *Node[V]) string {
 
 // Traverse traverses the tree with postorder traversal.
 func Traverse[V Value](tree *Tree[V], callback func(node *Node[V], depth int)) {
-	postOrderTraversal(tree.root, callback, 0)
+	postorderTraversal(tree.root, callback, 0)
+}
+
+// TraverseAll traverses the whole tree (include tombstones) with postorder traversal.
+func TraverseAll[V Value](tree *Tree[V], callback func(node *Node[V], depth int)) {
+	postorderTraversalAll(tree.root, callback, 0)
 }
 
 // Value represents the data stored in the nodes of Tree.
@@ -412,6 +429,28 @@ func (n *Node[V]) Prepend(children ...*Node[V]) {
 	}
 }
 
+// RemoveChild removes the given child.
+func (n *Node[V]) RemoveChild(child *Node[V]) {
+	if n.IsText() {
+		panic(errors.New("text node cannot have children"))
+	}
+	offset := -1
+
+	for i, c := range n.children {
+		if c == child {
+			offset = i
+			break
+		}
+	}
+
+	if offset == -1 {
+		panic(errors.New("child not found"))
+	}
+
+	n.children = append(n.children[:offset], n.children[offset+1:]...)
+	child.Parent = nil
+}
+
 // InsertBefore inserts the given node before the given child.
 func (n *Node[V]) InsertBefore(newNode, referenceNode *Node[V]) {
 	if n.IsText() {
@@ -632,7 +671,8 @@ func (t *Tree[V]) PathToTreePos(path []int) *TreePos[V] {
 	}
 
 	return &TreePos[V]{
-		Node: node,
+		Node:   node,
+		Offset: path[len(path)-1],
 	}
 }
 
diff --git a/pkg/splay/splay.go b/pkg/splay/splay.go
index a4512e2f..b6fbc195 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -241,7 +241,7 @@ func (t *Tree[V]) StructureAsString() string {
 // for debugging purpose.
 func (t *Tree[V]) CheckWeight() bool {
 	var nodes []*Node[V]
-	traversePostOrder(t.root, func(node *Node[V]) {
+	traversePostorder(t.root, func(node *Node[V]) {
 		nodes = append(nodes, node)
 	})
 	for _, node := range nodes {
@@ -325,7 +325,7 @@ func (t *Tree[V]) DeleteRange(leftBoundary, rightBoundary *Node[V]) {
 }
 
 func (t *Tree[V]) cutOffRight(root *Node[V]) {
-	traversePostOrder(root.right, func(node *Node[V]) { node.InitWeight() })
+	traversePostorder(root.right, func(node *Node[V]) { node.InitWeight() })
 	t.updateTreeWeight(root)
 }
 
@@ -407,13 +407,13 @@ func traverseInOrder[V Value](node *Node[V], callback func(node *Node[V])) {
 	traverseInOrder(node.right, callback)
 }
 
-func traversePostOrder[V Value](node *Node[V], callback func(node *Node[V])) {
+func traversePostorder[V Value](node *Node[V], callback func(node *Node[V])) {
 	if node == nil {
 		return
 	}
 
-	traversePostOrder(node.left, callback)
-	traversePostOrder(node.right, callback)
+	traversePostorder(node.left, callback)
+	traversePostorder(node.right, callback)
 	callback(node)
 }
 


Test patch:
diff --git a/pkg/document/crdt/root_test.go b/pkg/document/crdt/root_test.go
index 036fff0c..83eb4d19 100644
--- a/pkg/document/crdt/root_test.go
+++ b/pkg/document/crdt/root_test.go
@@ -26,9 +26,9 @@ import (
 	"github.com/yorkie-team/yorkie/test/helper"
 )
 
-func registerTextElementWithGarbage(fromPos, toPos *crdt.RGATreeSplitNodePos, root *crdt.Root, text crdt.TextElement) {
+func registerElementHasRemovedNodes(fromPos, toPos *crdt.RGATreeSplitNodePos, root *crdt.Root, text crdt.GCElement) {
 	if !fromPos.Equal(toPos) {
-		root.RegisterTextElementWithGarbage(text)
+		root.RegisterElementHasRemovedNodes(text)
 	}
 }
 
@@ -61,28 +61,28 @@ func TestRoot(t *testing.T) {
 		fromPos, toPos, _ := text.CreateRange(0, 0)
 		_, _, err := text.Edit(fromPos, toPos, nil, "Hello World", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, "Hello World", text.String())
 		assert.Equal(t, 0, root.GarbageLen())
 
 		fromPos, toPos, _ = text.CreateRange(5, 10)
 		_, _, err = text.Edit(fromPos, toPos, nil, "Yorkie", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, "HelloYorkied", text.String())
 		assert.Equal(t, 1, root.GarbageLen())
 
 		fromPos, toPos, _ = text.CreateRange(0, 5)
 		_, _, err = text.Edit(fromPos, toPos, nil, "", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, "Yorkied", text.String())
 		assert.Equal(t, 2, root.GarbageLen())
 
 		fromPos, toPos, _ = text.CreateRange(6, 7)
 		_, _, err = text.Edit(fromPos, toPos, nil, "", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, "Yorkie", text.String())
 		assert.Equal(t, 3, root.GarbageLen())
 
@@ -121,7 +121,7 @@ func TestRoot(t *testing.T) {
 			fromPos, toPos, _ := text.CreateRange(tc.from, tc.to)
 			_, _, err := text.Edit(fromPos, toPos, nil, tc.content, nil, ctx.IssueTimeTicket())
 			assert.NoError(t, err)
-			registerTextElementWithGarbage(fromPos, toPos, root, text)
+			registerElementHasRemovedNodes(fromPos, toPos, root, text)
 			assert.Equal(t, tc.want, text.String())
 			assert.Equal(t, tc.garbage, root.GarbageLen())
 		}
@@ -138,21 +138,21 @@ func TestRoot(t *testing.T) {
 		fromPos, toPos, _ := text.CreateRange(0, 0)
 		_, _, err := text.Edit(fromPos, toPos, nil, "Hello World", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, `[{"val":"Hello World"}]`, text.Marshal())
 		assert.Equal(t, 0, root.GarbageLen())
 
 		fromPos, toPos, _ = text.CreateRange(6, 11)
 		_, _, err = text.Edit(fromPos, toPos, nil, "Yorkie", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, `[{"val":"Hello "},{"val":"Yorkie"}]`, text.Marshal())
 		assert.Equal(t, 1, root.GarbageLen())
 
 		fromPos, toPos, _ = text.CreateRange(0, 6)
 		_, _, err = text.Edit(fromPos, toPos, nil, "", nil, ctx.IssueTimeTicket())
 		assert.NoError(t, err)
-		registerTextElementWithGarbage(fromPos, toPos, root, text)
+		registerElementHasRemovedNodes(fromPos, toPos, root, text)
 		assert.Equal(t, `[{"val":"Yorkie"}]`, text.Marshal())
 		assert.Equal(t, 2, root.GarbageLen())
 
diff --git a/test/integration/gc_test.go b/test/integration/gc_test.go
index 4d39b148..58d7ae06 100644
--- a/test/integration/gc_test.go
+++ b/test/integration/gc_test.go
@@ -26,6 +26,7 @@ import (
 
 	"github.com/yorkie-team/yorkie/pkg/document"
 	"github.com/yorkie-team/yorkie/pkg/document/json"
+	"github.com/yorkie-team/yorkie/pkg/document/time"
 	"github.com/yorkie-team/yorkie/test/helper"
 )
 
@@ -173,6 +174,152 @@ func TestGarbageCollection(t *testing.T) {
 		assert.Equal(t, 0, d2.GarbageLen())
 	})
 
+	t.Run("garbage collection for tree type test", func(t *testing.T) {
+		doc := document.New(helper.TestDocKey(t))
+
+		err := doc.Update(func(root *json.Object) error {
+			root.SetNewTree("t", &json.TreeNode{
+				Type: "doc",
+				Children: []json.TreeNode{{
+					Type: "p", Children: []json.TreeNode{{
+						Type: "tn", Children: []json.TreeNode{{
+							Type: "text", Value: "a",
+						}, {
+							Type: "text", Value: "b",
+						}},
+					}, {
+						Type: "tn", Children: []json.TreeNode{{
+							Type: "text", Value: "cd",
+						}},
+					}},
+				}},
+			})
+			assert.Equal(t, `<doc><p><tn>ab</tn><tn>cd</tn></p></doc>`, root.GetTree("t").ToXML())
+
+			return nil
+		})
+		assert.NoError(t, err)
+
+		err = doc.Update(func(root *json.Object) error {
+			root.GetTree("t").EditByPath([]int{0, 0, 0}, []int{0, 0, 2}, &json.TreeNode{Type: "text", Value: "gh"})
+			assert.Equal(t, `<doc><p><tn>gh</tn><tn>cd</tn></p></doc>`, root.GetTree("t").ToXML())
+			return nil
+		})
+
+		// [text(a), text(b)]
+		assert.NoError(t, err)
+		assert.Equal(t, doc.GarbageLen(), 2)
+		assert.Equal(t, doc.GarbageCollect(time.MaxTicket), 2)
+		assert.Equal(t, doc.GarbageLen(), 0)
+
+		err = doc.Update(func(root *json.Object) error {
+			root.GetTree("t").EditByPath([]int{0, 0, 0}, []int{0, 0, 2}, &json.TreeNode{Type: "text", Value: "cv"})
+			assert.Equal(t, `<doc><p><tn>cv</tn><tn>cd</tn></p></doc>`, root.GetTree("t").ToXML())
+			return nil
+		})
+
+		// [text(gh)]
+		assert.NoError(t, err)
+		assert.Equal(t, doc.GarbageLen(), 1)
+		assert.Equal(t, doc.GarbageCollect(time.MaxTicket), 1)
+		assert.Equal(t, doc.GarbageLen(), 0)
+
+		err = doc.Update(func(root *json.Object) error {
+			root.GetTree("t").EditByPath([]int{0}, []int{1}, &json.TreeNode{
+				Type: "p", Children: []json.TreeNode{{
+					Type: "tn", Children: []json.TreeNode{{
+						Type: "text", Value: "ab",
+					}},
+				}}})
+			assert.Equal(t, `<doc><p><tn>ab</tn></p></doc>`, root.GetTree("t").ToXML())
+			return nil
+		})
+
+		// [p, tn, tn, text(cv), text(cd)]
+		assert.NoError(t, err)
+		assert.Equal(t, doc.GarbageLen(), 5)
+		assert.Equal(t, doc.GarbageCollect(time.MaxTicket), 5)
+		assert.Equal(t, doc.GarbageLen(), 0)
+	})
+
+	t.Run("garbage collection for tree type test (multi clients)", func(t *testing.T) {
+		ctx := context.Background()
+		d1 := document.New(helper.TestDocKey(t))
+		err := c1.Attach(ctx, d1)
+		assert.NoError(t, err)
+
+		d2 := document.New(helper.TestDocKey(t))
+		err = c2.Attach(ctx, d2)
+		assert.NoError(t, err)
+
+		err = d1.Update(func(root *json.Object) error {
+			root.SetNewTree("t", &json.TreeNode{
+				Type: "doc",
+				Children: []json.TreeNode{{
+					Type: "p",
+					Children: []json.TreeNode{{
+						Type:     "tn",
+						Children: []json.TreeNode{{Type: "text", Value: "a"}, {Type: "text", Value: "b"}},
+					}, {
+						Type:     "tn",
+						Children: []json.TreeNode{{Type: "text", Value: "cd"}},
+					}},
+				}},
+			})
+			assert.Equal(t, `<doc><p><tn>ab</tn><tn>cd</tn></p></doc>`, root.GetTree("t").ToXML())
+			return nil
+		})
+		assert.NoError(t, err)
+		assert.Equal(t, 0, d1.GarbageLen())
+		assert.Equal(t, 0, d2.GarbageLen())
+
+		// (0, 0) -> (1, 0): syncedseqs:(0, 0)
+		err = c1.Sync(ctx)
+		assert.NoError(t, err)
+
+		// (1, 0) -> (1, 1): syncedseqs:(0, 0)
+		err = c2.Sync(ctx)
+		assert.NoError(t, err)
+
+		err = d2.Update(func(root *json.Object) error {
+			root.GetTree("t").EditByPath([]int{0, 0, 0}, []int{0, 0, 2}, &json.TreeNode{Type: "text", Value: "gh"})
+			return nil
+		})
+		assert.NoError(t, err)
+		assert.Equal(t, d1.GarbageLen(), 0)
+		assert.Equal(t, d2.GarbageLen(), 2)
+
+		// (1, 1) -> (1, 2): syncedseqs:(0, 1)
+		err = c2.Sync(ctx)
+		assert.NoError(t, err)
+		assert.Equal(t, d1.GarbageLen(), 0)
+		assert.Equal(t, d2.GarbageLen(), 2)
+
+		// (1, 2) -> (2, 2): syncedseqs:(1, 1)
+		err = c1.Sync(ctx)
+		assert.NoError(t, err)
+		assert.Equal(t, d1.GarbageLen(), 2)
+		assert.Equal(t, d2.GarbageLen(), 2)
+
+		// (2, 2) -> (2, 2): syncedseqs:(1, 2)
+		err = c2.Sync(ctx)
+		assert.NoError(t, err)
+		assert.Equal(t, d1.GarbageLen(), 2)
+		assert.Equal(t, d2.GarbageLen(), 2)
+
+		// (2, 2) -> (2, 2): syncedseqs:(2, 2): meet GC condition
+		err = c1.Sync(ctx)
+		assert.NoError(t, err)
+		assert.Equal(t, d1.GarbageLen(), 0)
+		assert.Equal(t, d2.GarbageLen(), 2)
+
+		// (2, 2) -> (2, 2): syncedseqs:(2, 2): meet GC condition
+		err = c2.Sync(ctx)
+		assert.NoError(t, err)
+		assert.Equal(t, d1.GarbageLen(), 0)
+		assert.Equal(t, d2.GarbageLen(), 0)
+	})
+
 	t.Run("garbage collection with detached document test", func(t *testing.T) {
 		ctx := context.Background()
 		d1 := document.New(helper.TestDocKey(t))