classNode# children is a dict for draw_general_tree and a list for build_nary_treedef__init__(val,children=none)self.val,self.children=val,childrenisnone?{}:children
Utility function to build a binary tree from a level-order list representation.
Null/None values are skipped for node creation.
Source code in pydsa/tree.mu
2425262728293031323334353637
defbuild_tree(arr:[int?])->TreeNode?""" Utility function to build a binary tree from a level-order list representation. Null/None values are skipped for node creation. """ifnotarrorarr[0]isnone# should this be [] ?returnnonenodes=[visnone?none:TreeNode(v)forvinarr]kids=iter(nodes[1:])fornodeinnodesifnodenode.left,node.right=next(kids,none),next(kids,none)nodes[0]
46474849505152535455565758
defbuild_tree(arr:list[Optional[int]])->Optional[TreeNode]:""" Utility function to build a binary tree from a level-order list representation. Null/None values are skipped for node creation. """ifnotarrorarr[0]isNone:returnNonenodes=[NoneifvisNoneelseTreeNode(v)forvinarr]kids=iter(nodes[1:])fornodeinnodes:ifnode:node.left,node.right=next(kids,None),next(kids,None)returnnodes[0]
Utility function to draw a binary tree in the terminal using PrettyPrintTree.
Requires 'PrettyPrintTree' library: pip install PrettyPrintTree
For colors, requires 'colorama': pip install colorama
Supports node.color attribute for coloring the node value (e.g., 'blue', 'red', etc.).
Source code in pydsa/tree.mu
394041424344454647484950515253545556575859
defdraw_tree(root:TreeNode?)->none""" Utility function to draw a binary tree in the terminal using PrettyPrintTree. Requires 'PrettyPrintTree' library: pip install PrettyPrintTree For colors, requires 'colorama': pip install colorama Supports node.color attribute for coloring the node value (e.g., 'blue', 'red', etc.). """ifnotrootprint"Empty tree"returnprint"\n"defget_value(node:TreeNode)->strretval_str=str(node.val)ifhasattr(node,"color")fromcoloramaimportFore,Stylecolor=node.color.lower()ifcolorin"black red green yellow blue magenta cyan white".split()val_str=getattr(Fore,color.upper())+val_str+Style.RESET_ALLdefget_children(node:TreeNode):[cforcin(node.left,node.right)ifc]pt=_pretty_print_tree()(get_children,get_value,border=true,color="\x1b[30;43m")pt(root)
6162636465666768697071727374757677787980818283
defdraw_tree(root:Optional[TreeNode])->None:""" Utility function to draw a binary tree in the terminal using PrettyPrintTree. Requires 'PrettyPrintTree' library: pip install PrettyPrintTree For colors, requires 'colorama': pip install colorama Supports node.color attribute for coloring the node value (e.g., 'blue', 'red', etc.). """ifnotroot:print("Empty tree")returnprint("\n")defget_value(node:TreeNode)->str:val_str=str(node.val)ifhasattr(node,"color"):fromcoloramaimportFore,Stylecolor=node.color.lower()ifcolorin"black red green yellow blue magenta cyan white".split():val_str=getattr(Fore,color.upper())+val_str+Style.RESET_ALLreturnval_strdefget_children(node:TreeNode):return[cforcin(node.left,node.right)ifc]pt=_pretty_print_tree()(get_children,get_value,border=True,color="\x1b[30;43m")pt(root)
Generates a full (perfect) binary tree of the given height.
Height 0 returns a single node.
Node values are assigned sequentially from 1 in level-order.
Source code in pydsa/tree.mu
76777879808182838485
defgenerate_full_binary_tree(height:int)->TreeNode?""" Generates a full (perfect) binary tree of the given height. Height 0 returns a single node. Node values are assigned sequentially from 1 in level-order. """ifheight<0returnnone# a perfect binary tree of height h has 2^(h+1) - 1 nodesbuild_tree(1..<(1<<(height+1)))
105106107108109110111112113
defgenerate_full_binary_tree(height:int)->Optional[TreeNode]:""" Generates a full (perfect) binary tree of the given height. Height 0 returns a single node. Node values are assigned sequentially from 1 in level-order. """ifheight<0:returnNonereturnbuild_tree(range(1,(1<<(height+1))))
The tree grows one node at a time. Each new node fills one of the empty
child slots of the tree so far. Which slot is chosen is controlled by:
sparsity in [0, 1]: 0 fills the shallowest slots first, so the tree is
as bushy as a complete tree; 1 fills the deepest slots, so the tree
is a long chain. In between, each node picks deep with probability
sparsity and shallow otherwise.
skew in [-1, 1]: -1 always takes a left slot when one is available at
the chosen depth, 1 always takes a right one, 0 is even.
values: the node values, in the order the tree grows; default is 1..size shuffled.
With bst=True the values are sorted and assigned in inorder, so the
tree is a valid BST with the same shape.
seed: fixes the tree; the global random state is untouched.
defgenerate_random_tree(size:int,seed:int?=none,sparsity:float=0.0,skew:float=0.0,values:Iterable[int]?=none,bst:bool=false)->TreeNode?"""A random binary tree with `size` nodes. The tree grows one node at a time. Each new node fills one of the empty child slots of the tree so far. Which slot is chosen is controlled by: sparsity in [0, 1]: 0 fills the shallowest slots first, so the tree is as bushy as a complete tree; 1 fills the deepest slots, so the tree is a long chain. In between, each node picks deep with probability `sparsity` and shallow otherwise. skew in [-1, 1]: -1 always takes a left slot when one is available at the chosen depth, 1 always takes a right one, 0 is even. values: the node values, in the order the tree grows; default is 1..size shuffled. With bst=True the values are sorted and assigned in inorder, so the tree is a valid BST with the same shape. seed: fixes the tree; the global random state is untouched. """ifsize<=0returnnonerng=random.Random(seed)vals=valuesisnone?list(1..size):list(values)iflen(vals)!=sizeraiseValueError(f"need {size} values, got {len(vals)}")ifvaluesisnonerng.shuffle(vals)retroot=TreeNode(vals[0])# (depth, parent, side): every empty child slot in the tree so farslots=[(1,root,"left"),(1,root,"right")]forvinvals[1:]depth=(rng.random()<sparsity?max:min)(s[0]forsinslots)at=[sforsinslotsifs[0]==depth]side=rng.random()<(1+skew)/2?"right":"left"depth,parent,name=rng.choice([sforsinatifs[2]==side]orat)slots.remove((depth,parent,name))child=TreeNode(v)setattr(parent,name,child)slots+=[(depth+1,child,"left"),(depth+1,child,"right")]ifbststack,node=[],rootforvinsorted(vals)whilenodestack<-nodenode=node.leftnode=stack.node.val=vnode=node.right
defgenerate_random_tree(size:int,seed:Optional[int]=None,sparsity:float=0.0,skew:float=0.0,values:Optional[Iterable[int]]=None,bst:bool=False)->Optional[TreeNode]:"""A random binary tree with `size` nodes. The tree grows one node at a time. Each new node fills one of the empty child slots of the tree so far. Which slot is chosen is controlled by: sparsity in [0, 1]: 0 fills the shallowest slots first, so the tree is as bushy as a complete tree; 1 fills the deepest slots, so the tree is a long chain. In between, each node picks deep with probability `sparsity` and shallow otherwise. skew in [-1, 1]: -1 always takes a left slot when one is available at the chosen depth, 1 always takes a right one, 0 is even. values: the node values, in the order the tree grows; default is 1..size shuffled. With bst=True the values are sorted and assigned in inorder, so the tree is a valid BST with the same shape. seed: fixes the tree; the global random state is untouched. """ifsize<=0:returnNonerng=random.Random(seed)vals=list(range(1,size+1))ifvaluesisNoneelselist(values)iflen(vals)!=size:raiseValueError(f"need {size} values, got {len(vals)}")ifvaluesisNone:rng.shuffle(vals)root=TreeNode(vals[0])slots=[(1,root,"left"),(1,root,"right")]forvinvals[1:]:depth=(maxifrng.random()<sparsityelsemin)(s[0]forsinslots)at=[sforsinslotsifs[0]==depth]side="right"ifrng.random()<(1+skew)/2else"left"depth,parent,name=rng.choice([sforsinatifs[2]==side]orat)slots.remove((depth,parent,name))child=TreeNode(v)setattr(parent,name,child)slots+=[(depth+1,child,"left"),(depth+1,child,"right")]ifbst:stack,node=[],rootforvinsorted(vals):whilenode:stack.append(node)node=node.leftnode=stack.pop()node.val=vnode=node.rightreturnroot
defbuild_nary_tree(arr:[int?])->Node?ifnotarrorarr[0]isnonereturnnoneretroot=Node(arr[0],children=[])queue,vals=[root],iter(arr[2:])# skip the first null at index 1fornodeinqueueforvinvalsifvisnonebreak# a null ends the children of this nodenode.children<-Node(v,children=[])queue+=node.children
A general tree from its nested form [val, [child, child, ...]], where
each child is again [val, [...]]. Children get keys 0, 1, 2, ...
Source code in pydsa/tree.mu
170171172173174175176
defbuild_general_tree(nested:[Any])->GeneralNode"""A general tree from its nested form [val, [child, child, ...]], where each child is again [val, [...]]. Children get keys 0, 1, 2, ..."""val,kids=nestedretnode=GeneralNode(val)for>i,kidinkidsnode.children[i]=build_general_tree(kid)
203204205206207208209210
defbuild_general_tree(nested:list[Any])->GeneralNode:"""A general tree from its nested form [val, [child, child, ...]], where each child is again [val, [...]]. Children get keys 0, 1, 2, ..."""val,kids=nestednode=GeneralNode(val)fori,kidinenumerate(kids):node.children[i]=build_general_tree(kid)returnnode
The nested form [val, [child, child, ...]] of a general tree, the
inverse of build_general_tree. Children come in the order of .children.
Source code in pydsa/tree.mu
178179180181182183
defget_general_tree(root:GeneralNode?)->[Any]?"""The nested form [val, [child, child, ...]] of a general tree, the inverse of build_general_tree. Children come in the order of .children."""ifrootisnotnonekids=isinstance(root.children,dict)?root.children.values():root.children[root.val,[get_general_tree(kid)forkidinkids]]
213214215216217218
defget_general_tree(root:Optional[GeneralNode])->Optional[list[Any]]:"""The nested form [val, [child, child, ...]] of a general tree, the inverse of build_general_tree. Children come in the order of .children."""ifrootisnotNone:kids=root.children.values()ifisinstance(root.children,dict)elseroot.childrenreturn[root.val,[get_general_tree(kid)forkidinkids]]