Succinct Encoding of Binary Tree | Node structure ; This function fills lists ' struc ' and ' data ' . ' struc ' list stores structure information . ' data ' list stores tree data ; If root is None , put 0 in structure array and return ; Else place 1 in structure array , key in ' data ' array and recur for left and right children ; Constructs tree from ' struc ' and 'data   ; Remove one item from structure list ; If removed bit is 1 ; Remove an item from data list ; Create a tree node with removed data ; And recur to create left and right subtrees ; A utility function to print tree ; Let us conthe Tree shown in the above figure ; Structure iterator ; Data iterator
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def EncodeSuccint ( root , struc , data ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT struc . append ( 0 ) NEW_LINE return NEW_LINE DEDENT struc . append ( 1 ) NEW_LINE data . append ( root . key ) NEW_LINE EncodeSuccint ( root . left , struc , data ) NEW_LINE EncodeSuccint ( root . right , struc , data ) NEW_LINE DEDENT def DecodeSuccinct ( struc , data ) : NEW_LINE INDENT if ( len ( struc ) <= 0 ) : NEW_LINE INDENT return None NEW_LINE DEDENT b = struc [ 0 ] NEW_LINE struc . pop ( 0 ) NEW_LINE if b == 1 : NEW_LINE INDENT key = data [ 0 ] NEW_LINE data . pop ( 0 ) NEW_LINE root = Node ( key ) NEW_LINE root . left = DecodeSuccinct ( struc , data ) ; NEW_LINE root . right = DecodeSuccinct ( struc , data ) ; NEW_LINE return root NEW_LINE DEDENT return None NEW_LINE DEDENT def preorder ( root ) : NEW_LINE INDENT if root is not None : NEW_LINE INDENT print " key : ▁ % d " % ( root . key ) , NEW_LINE if root . left is not None : NEW_LINE INDENT print " | ▁ left ▁ child : ▁ % d " % ( root . left . key ) , NEW_LINE DEDENT if root . right is not None : NEW_LINE INDENT print " | ▁ right ▁ child ▁ % d " % ( root . right . key ) , NEW_LINE DEDENT print " " NEW_LINE preorder ( root . left ) NEW_LINE preorder ( root . right ) NEW_LINE DEDENT DEDENT root = Node ( 10 ) NEW_LINE root . left = Node ( 20 ) NEW_LINE root . right = Node ( 30 ) NEW_LINE root . left . left = Node ( 40 ) NEW_LINE root . left . right = Node ( 50 ) NEW_LINE root . right . right = Node ( 70 ) NEW_LINE print " Given ▁ Tree " NEW_LINE preorder ( root ) NEW_LINE struc = [ ] NEW_LINE data = [ ] NEW_LINE EncodeSuccint ( root , struc , data ) NEW_LINE print   " NEW_LINE Encoded Tree " NEW_LINE print " Structure ▁ List " NEW_LINE for i in struc : NEW_LINE INDENT print i , NEW_LINE DEDENT print   " NEW_LINE DataList " NEW_LINE for value in data : NEW_LINE INDENT print value , NEW_LINE DEDENT newroot = DecodeSuccinct ( struc , data ) NEW_LINE print   " NEW_LINE Preorder Traversal of decoded tree " NEW_LINE preorder ( newroot ) NEW_LINE