Coding Interview Problem #3
Given the root of a binary tree, implement:
which serializes the tree into a string and:
which deserializes the string back into the tree.
Diagram goes here
- What is serialization?
- What is deserialization?
- How to traverse a binary tree?
- How to represent a binary tree in code?
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
- Node can have left and right
- Node has left only
- Node has right only
- Node has no children
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.
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...
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