Skip to content

pydsa.tree

Node

Source code in pydsa/tree.mu
15
16
17
18
class Node
  # children is a dict for draw_general_tree and a list for build_nary_tree
  def __init__(val, children=none)
    self.val, self.children = val, children is none ? {} : children
36
37
38
class Node:
    def __init__(self, val, children=None):
        self.val, self.children = val, Rec() if children is None else children

find_node

find_node(root, val)
Source code in pydsa/tree.mu
20
21
22
def find_node(root, val)
  if root
    root.val == val ? root : find_node(root.left, val) or find_node(root.right, val)
41
42
43
def find_node(root, val):
    if root:
        return root if root.val == val else find_node(root.left, val) or find_node(root.right, val)

build_tree

build_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.

Source code in pydsa/tree.mu
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def build_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.
  """
  if not arr or arr[0] is none
    # should this be [] ?
    return none
  nodes = [v is none ? none : TreeNode(v) for v in arr]
  kids = iter(nodes[1:])
  for node in nodes
    if node
      node.left, node.right = next(kids, none), next(kids, none)
  nodes[0]
46
47
48
49
50
51
52
53
54
55
56
57
58
def build_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.
    """
    if not arr or arr[0] is None:
        return None
    nodes = [None if v is None else TreeNode(v) for v in arr]
    kids = iter(nodes[1:])
    for node in nodes:
        if node:
            node.left, node.right = next(kids, None), next(kids, None)
    return nodes[0]

draw_tree

draw_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.).

Source code in pydsa/tree.mu
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def draw_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.).
  """
  if not root
    print "Empty tree"
    return
  print "\n"
  def get_value(node: TreeNode) -> str
    ret val_str = str(node.val)
    if hasattr(node, "color")
      from colorama import Fore, Style
      color = node.color.lower()
      if color in "black red green yellow blue magenta cyan white".split()
        val_str = getattr(Fore, color.upper()) + val_str + Style.RESET_ALL
  def get_children(node: TreeNode): [c for c in (node.left, node.right) if c]
  pt = _pretty_print_tree()(get_children, get_value, border=true, color="\x1b[30;43m")
  pt(root)
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
def draw_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.).
    """
    if not root:
        print("Empty tree")
        return
    print("\n")
    def get_value(node: TreeNode) -> str:
        val_str = str(node.val)
        if hasattr(node, "color"):
            from colorama import Fore, Style
            color = node.color.lower()
            if color in "black red green yellow blue magenta cyan white".split():
                val_str = getattr(Fore, color.upper()) + val_str + Style.RESET_ALL
        return val_str
    def get_children(node: TreeNode):
        return [c for c in (node.left, node.right) if c]
    pt = _pretty_print_tree()(get_children, get_value, border=True, color="\x1b[30;43m")
    pt(root)

draw_general_tree

draw_general_tree(root: Optional[Node]) -> None
Source code in pydsa/tree.mu
64
65
66
67
68
69
70
71
72
73
74
def draw_general_tree(root: Node?) -> none
  if not root
    print "Empty tree"
    return
  print "\n"
  def get_children(w: _Wrapper)
    kids = w.node.children
    [_Wrapper(kid) for kid in (isinstance(kids, dict) ? kids.values() : kids)]
  def get_value(w: _Wrapper): str(hasattr(w.node, "label") ? w.node.label : w.node.val)
  pt = _pretty_print_tree()(get_children, get_value, border=true, color="\x1b[30;43m")
  pt(_Wrapper(root))
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
def draw_general_tree(root: Optional[Node]) -> None:
    if not root:
        print("Empty tree")
        return
    print("\n")
    def get_children(w: _Wrapper):
        kids = w.node.children
        return [_Wrapper(kid) for kid in (kids.values() if isinstance(kids, dict) else kids)]
    def get_value(w: _Wrapper):
        return str(w.node.label if hasattr(w.node, "label") else w.node.val)
    pt = _pretty_print_tree()(get_children, get_value, border=True, color="\x1b[30;43m")
    pt(_Wrapper(root))

generate_full_binary_tree

generate_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.

Source code in pydsa/tree.mu
76
77
78
79
80
81
82
83
84
85
def generate_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.
  """
  if height < 0
    return none
  # a perfect binary tree of height h has 2^(h+1) - 1 nodes
  build_tree(1..<(1 << (height + 1)))
105
106
107
108
109
110
111
112
113
def generate_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.
    """
    if height < 0:
        return None
    return build_tree(range(1, (1 << (height + 1))))

generate_random_tree

generate_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.

Source code in pydsa/tree.mu
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
def generate_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.
  """
  if size <= 0
    return none
  rng = random.Random(seed)
  vals = values is none ? list(1..size) : list(values)
  if len(vals) != size
    raise ValueError(f"need {size} values, got {len(vals)}")
  if values is none
    rng.shuffle(vals)
  ret root = TreeNode(vals[0])
  # (depth, parent, side): every empty child slot in the tree so far
  slots = [(1, root, "left"), (1, root, "right")]
  for v in vals[1:]
    depth = (rng.random() < sparsity ? max : min)(s[0] for s in slots)
    at = [s for s in slots if s[0] == depth]
    side = rng.random() < (1 + skew) / 2 ? "right" : "left"
    depth, parent, name = rng.choice([s for s in at if s[2] == side] or at)
    slots.remove((depth, parent, name))
    child = TreeNode(v)
    setattr(parent, name, child)
    slots += [(depth + 1, child, "left"), (depth + 1, child, "right")]
  if bst
    stack, node = [], root
    for v in sorted(vals)
      while node
        stack <- node
        node = node.left
      node = stack .
      node.val = v
      node = node.right
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
def generate_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.
    """
    if size <= 0:
        return None
    rng = random.Random(seed)
    vals = list(range(1, size + 1)) if values is None else list(values)
    if len(vals) != size:
        raise ValueError(f"need {size} values, got {len(vals)}")
    if values is None:
        rng.shuffle(vals)
    root = TreeNode(vals[0])
    slots = [(1, root, "left"), (1, root, "right")]
    for v in vals[1:]:
        depth = (max if rng.random() < sparsity else min)(s[0] for s in slots)
        at = [s for s in slots if s[0] == depth]
        side = "right" if rng.random() < (1 + skew) / 2 else "left"
        depth, parent, name = rng.choice([s for s in at if s[2] == side] or at)
        slots.remove((depth, parent, name))
        child = TreeNode(v)
        setattr(parent, name, child)
        slots += [(depth + 1, child, "left"), (depth + 1, child, "right")]
    if bst:
        stack, node = [], root
        for v in sorted(vals):
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            node.val = v
            node = node.right
    return root

get_inorder

get_inorder(root: Optional[TreeNode]) -> list[int]
Source code in pydsa/tree.mu
137
138
def get_inorder(root: TreeNode?) -> [int]
  root ? get_inorder(root.left) + [root.val] + get_inorder(root.right) : []
164
165
def get_inorder(root: Optional[TreeNode]) -> list[int]:
    return get_inorder(root.left) + [root.val] + get_inorder(root.right) if root else []

is_balanced

is_balanced(root: Optional[TreeNode]) -> bool
Source code in pydsa/tree.mu
140
141
142
143
144
145
146
147
def is_balanced(root: TreeNode?) -> bool
  def check_height(node: TreeNode?) -> int
    if not node
      return 0
    left = check_height(node.left)
    right = left == -1 ? -1 : check_height(node.right)
    right == -1 or abs(left - right) > 1 ? -1 : max(left, right) + 1
  check_height(root) != -1
168
169
170
171
172
173
174
175
def is_balanced(root: Optional[TreeNode]) -> bool:
    def check_height(node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        left = check_height(node.left)
        right = -1 if left == -1 else check_height(node.right)
        return -1 if right == -1 or abs(left - right) > 1 else max(left, right) + 1
    return check_height(root) != -1

get_level_order

get_level_order(
    root: Optional[TreeNode],
) -> list[Optional[int]]
Source code in pydsa/tree.mu
149
150
151
152
153
154
155
156
def get_level_order(root: TreeNode?) -> [int?]
  ret vals, nodes = [], [root]
  for node in nodes
    vals <- node ? node.val : none
    if node
      nodes += [node.left, node.right]
  while vals and vals[-1] is none
    vals .
178
179
180
181
182
183
184
185
186
def get_level_order(root: Optional[TreeNode]) -> list[Optional[int]]:
    vals, nodes = [], [root]
    for node in nodes:
        vals.append(node.val if node else None)
        if node:
            nodes += [node.left, node.right]
    while vals and vals[-1] is None:
        vals.pop()
    return vals

build_nary_tree

build_nary_tree(arr: list[Optional[int]]) -> Optional[Node]
Source code in pydsa/tree.mu
158
159
160
161
162
163
164
165
166
167
168
def build_nary_tree(arr: [int?]) -> Node?
  if not arr or arr[0] is none
    return none
  ret root = Node(arr[0], children=[])
  queue, vals = [root], iter(arr[2:])  # skip the first null at index 1
  for node in queue
    for v in vals
      if v is none
        break  # a null ends the children of this node
      node.children <- Node(v, children=[])
    queue += node.children
189
190
191
192
193
194
195
196
197
198
199
200
def build_nary_tree(arr: list[Optional[int]]) -> Optional[Node]:
    if not arr or arr[0] is None:
        return None
    root = Node(arr[0], children=[])
    queue, vals = [root], iter(arr[2:])
    for node in queue:
        for v in vals:
            if v is None:
                break
            node.children.append(Node(v, children=[]))
        queue += node.children
    return root

build_general_tree

build_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, ...

Source code in pydsa/tree.mu
170
171
172
173
174
175
176
def build_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 = nested
  ret node = GeneralNode(val)
  for >i, kid in kids
    node.children[i] = build_general_tree(kid)
203
204
205
206
207
208
209
210
def build_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 = nested
    node = GeneralNode(val)
    for i, kid in enumerate(kids):
        node.children[i] = build_general_tree(kid)
    return node

get_general_tree

get_general_tree(
    root: Optional[Node],
) -> 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.

Source code in pydsa/tree.mu
178
179
180
181
182
183
def get_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."""
  if root is not none
    kids = isinstance(root.children, dict) ? root.children.values() : root.children
    [root.val, [get_general_tree(kid) for kid in kids]]
213
214
215
216
217
218
def get_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."""
    if root is not None:
        kids = root.children.values() if isinstance(root.children, dict) else root.children
        return [root.val, [get_general_tree(kid) for kid in kids]]