Serialize and Deserialize Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Serialization with Preorder Traversal

What is the output of the serialization function when applied to this binary tree?

Tree structure:
1
/ \
2 3
/ \
4 5

The serialization uses preorder traversal with '#' for null nodes and commas as separators.

DSA Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func serialize(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    leftSerialized := serialize(root.Left)
    rightSerialized := serialize(root.Right)
    return fmt.Sprintf("%d,%s,%s", root.Val, leftSerialized, rightSerialized)
}

// Tree construction
root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{3, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}}

fmt.Println(serialize(root))

A 1,2,#,#,3,4,#,#,5,#,#

B 1,2,#,#,3,4,#,#,5,#

C 1,2,#,3,4,#,#,5,#,#

D 1,2,#,#,3,4,#,5,#,#,#

💡 Hint

Remember preorder traversal visits root, then left subtree, then right subtree. Null children are marked with '#'.

The serialization visits nodes in preorder: root, left, right. Null children are represented by '#'. So the output is "1,2,#,#,3,4,#,#,5,#,#".

❓ Predict Output

intermediate

Result of Deserializing a Serialized String

Given the serialized string "1,2,#,#,3,#,4,#,#", what is the value of the right child of the root after deserialization?

DSA Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    var index int
    var build func() *TreeNode
    build = func() *TreeNode {
        if vals[index] == "#" {
            index++
            return nil
        }
        val, _ := strconv.Atoi(vals[index])
        index++
        node := &TreeNode{Val: val}
        node.Left = build()
        node.Right = build()
        return node
    }
    return build()
}

root := deserialize("1,2,#,#,3,#,4,#,#")
fmt.Println(root.Right.Val)

A 0

B 4

C 3

D nil (no right child)

💡 Hint

Trace the deserialization step by step, matching preorder nodes and nulls.

The root is 1, left child is 2 with no children, right child is 3 with no left child and right child 4. So root.Right.Val is 3.

🧠 Conceptual

advanced

Understanding Null Markers in Serialization

Why is it necessary to include a special marker (like '#') for null nodes when serializing a binary tree using preorder traversal?

A To indicate the end of the serialized string

B To distinguish between left and right children during deserialization

C To reduce the size of the serialized string

D To mark nodes that have only one child

💡 Hint

Think about how the deserialization function knows when to stop building a subtree.

Null markers tell the deserialization function where a child is missing, so it can correctly reconstruct the tree structure and distinguish left from right children.

❓ Predict Output

advanced

Output of Deserialization Followed by Serialization

What is the output of serializing the tree obtained by deserializing the string "1,#,2,#,3,#,#" using the given serialize and deserialize functions?

DSA Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func serialize(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    leftSerialized := serialize(root.Left)
    rightSerialized := serialize(root.Right)
    return fmt.Sprintf("%d,%s,%s", root.Val, leftSerialized, rightSerialized)
}

func deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    var index int
    var build func() *TreeNode
    build = func() *TreeNode {
        if vals[index] == "#" {
            index++
            return nil
        }
        val, _ := strconv.Atoi(vals[index])
        index++
        node := &TreeNode{Val: val}
        node.Left = build()
        node.Right = build()
        return node
    }
    return build()
}

root := deserialize("1,#,2,#,3,#,#")
fmt.Println(serialize(root))

A 1,#,2,#,#

B 1,#,2,#,3,#

C 1,#,2,#,3,#,#,#

D 1,#,2,#,3,#,#

💡 Hint

The deserialized tree is skewed to the right. Serialization should reproduce the same string.

Deserializing then serializing returns the same preorder string with null markers, preserving the tree shape exactly.

🚀 Application

expert

Count Nodes from Serialized String Without Full Deserialization

Given a serialized binary tree string using preorder traversal with '#' for nulls, which approach correctly counts the total number of non-null nodes without building the tree?

A Use a stack to simulate preorder traversal, increment count for each number, and skip '#' markers

B Count all values that are not '#' by splitting the string by commas

C Count the number of commas and subtract the number of '#' markers

D Traverse the string and increment count only when a number is followed by two '#' markers

💡 Hint

Think about how preorder traversal works and how nulls affect node counting.

Using a stack to simulate traversal allows counting nodes correctly without building the tree. Simply counting non-'#' values may overcount if not careful.