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.

Breadth First Traversal

  • 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])

Exciting revisions to this article coming soon...


Related Articles


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.