Serializing and Deserializing Binary Tree Prereq: DFS on Tree
Given a binary tree, write a serialize function that converts the tree into a string and a deserialize function that converts a string to a binary tree. You may serialize the tree into any string representation you want as long as it can be deseralized.
Try it yourself
Explanation To serialize, we can simply do a DFS and append the node value to the string. We need to encode null nodes too since otherwise we wouldn't be able to tell if we have reached leaf nodes when we deserialize. We use x here as a placeholder for the null node.
To deserialize, we split the string into tokens and consume them. For each token we create a new node using token value. When we see an x we know we reached the leaf and return.
Python Java JavaScript Expand 4 lines ... 5 5 self.right = right 6 6 7 7 def serialize ( root ): 8 - # WRITE YOUR BRILLIANT CODE HERE 8 + res = [] 9 + def dfs ( root ): 10 + if not root: 11 + res.append( 'x' ) 12 + return 13 + res.append(root.val) 14 + dfs(root.left) 15 + dfs(root.right) 16 + dfs(root) 17 + return ' ' .join(res) 18 + 9 19 def deserialize ( s ): 10 - # AND HERE 20 + def dfs ( nodes ): 21 + val = next(nodes) 22 + if val == 'x' : return 23 + cur = Node(int(val)) 24 + cur.left = dfs(nodes) 25 + cur.right = dfs(nodes) 26 + return cur 27 + # create an iterator that returns a token each time we call `next` 28 + return dfs(iter(s.split())) 29 + 11 30 if __name__ == "__main__" : 12 31 # driver code, do not modify 13 32 def build_tree ( nodes ): 14 33 val = next(nodes) 15 34 if not val or val == 'x' : return Expand 14 lines ...
Expand 2 lines ... 3 3 import java.util.Iterator; 4 4 import java.util.List; 5 5 import java.util.Scanner; 6 + import java.util.StringJoiner; 6 7 class Solution { 7 8 8 9 public static String serialize (Node root) { 9 - // WRITE YOUR BRILLIANT CODE HERE 10 + StringJoiner res = new StringJoiner( " " ); 11 + serializeDFS(root, res); 12 + return res.toString(); 10 13 } 11 14 15 + private static void serializeDFS (Node root, StringJoiner result) { 16 + if (root == null ) { 17 + result.add( "x" ); 18 + return ; 19 + } 20 + result.add(Integer.toString(root.val)); 21 + serializeDFS(root.left, result); 22 + serializeDFS(root.right, result); 23 + } 24 + 12 25 public static Node deserialize (String root) { 13 - // AND HERE 26 + // create an iterator that returns a token each time we call `next` 27 + return deserializeDFS(Arrays.stream(root.split( " " )).iterator()); 14 28 } 15 29 30 + private static Node deserializeDFS (Iterator<String> nodes) { 31 + String val = nodes.next(); 32 + if (val.equals( "x" )) return null ; 33 + Node cur = new Node(Integer.parseInt(val)); 34 + cur.left = deserializeDFS(nodes); 35 + cur.right = deserializeDFS(nodes); 36 + return cur; 37 + } 38 + 16 39 /** Driver class, do not change **/ 17 40 static class Node { 18 41 int val; 19 42 Node left, right; 20 43 Expand 35 lines ...
Expand 8 lines ... 9 9 } 10 10 11 11 function serialize ( root ) { 12 - // WRITE YOUR BRILLIANT CODE HERE 12 + let res = []; 13 + serialize_dfs(root, res); 14 + return res.join( " " ); 13 15 } 14 16 17 + function serialize_dfs ( root, res ) { 18 + if (!root) { 19 + res.push( "x" ); 20 + return ; 21 + } 22 + res.push(root.val); 23 + serialize_dfs(root.left, res); 24 + serialize_dfs(root.right, res); 25 + } 26 + 15 27 function deserialize ( s ) { 16 - // AND HERE 28 + // create an iterator that returns a token each time we call `next` 29 + return deserialize_dfs(s.split( " " )[ Symbol .iterator]()); 17 30 } 18 31 32 + function deserialize_dfs ( nodes ) { 33 + let val = nodes.next().value; 34 + if (val === 'x' ) return ; 35 + const cur = new Node( parseInt (val, 10 )); 36 + cur.left = deserialize_dfs(nodes); 37 + cur.right = deserialize_dfs(nodes); 38 + return cur; 39 + } 40 + 19 41 function build_tree ( nodes ) { 20 42 let val = nodes.next().value; 21 43 if (!val || val === 'x' ) return ; 22 44 let cur = new Node( parseInt (val, 10 )); 23 45 cur.left = build_tree(nodes); Expand 23 lines ...
