# Coding Interview Problem #3

Given the root of a binary tree, implement:

``````def serialize(root)
``````

which serializes the tree into a string and:

``````def deserialize(string)
``````

which deserializes the string back into the tree.

Example

Goes here
Diagram goes here

Test Case

Goes here

## PreRequisite Knowledge

• What is serialization?
• What is deserialization?
• How to traverse a binary tree?
• How to represent a binary tree in code?

### Serialization

Serialization is the process of converting a data structure or object into a sequence of bits. It can be stored in a file or transmitted across a network to be reconstructed in another computer.

### Binary Search Tree

Binary Search Tree is a Binary Tree with these properties:

• Each node contains one key
• Keys in the left subtree < Key in the parent node
• Keys in the right subtree > Key in its parent
• No duplicate keys

## Cases

• Node can have left and right
• Node has left only
• Node has right only
• Node has no children

## Traversal Types

### Depth First Traversals

• Pre Order (node left right)
• In Order (left node right)
• Post Order (left right node)

Diagrams to represent goes here.

If a binary tree is traversed in-order, the output will be sorted in an ascending order. Binary Tree is a recursive data structure.

• Lever Order (Top to bottom, left to right)

BFS will traverse the tree one level at a time. We will traverse root, root-left, root-right, root-left-left, root-left-right and so on. So, the serialized string will be 1,2,3,4,5,#,#,6.

## Pseudocode

``````InOrder-Traversal(x)
if x == nil return
InOrder-Traversal(left[x])
print key[x]
InOrder-Traversal(right[x])
``````

# Ace the Technical Interview

• Easily find the gaps in your knowledge
• Get customized lessons based on where you are
• Take consistent action everyday
• Builtin accountability to keep you on track
• You will solve bigger problems over time
• Get the job of your dreams

#### Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.