pytudes._2021.utils.binary_tree

See Also:

• pytudes/_2021/educative/grokking_the_coding_interview/tree_bfs/_1_binary_tree_level_order_traversal__easy.py

• pytudes/_2021/leetcode/blind_75/tree/_104__maximum_depth_of_binary_tree__easy.py

Module Contents

Classes

TreeNode

Functions

_build_tree(arr, root_idx)	Recursively builds the tree rooted at arr[root_idx]
build_tree(arr[, is_1_indexed])	Builds a TreeNode binary tree from the values in arr
get_child_idx_left(index)	Args:
get_child_idx_right(index)	Args:
get_parent_idx(index)	Args:

Attributes

TreeNodeType

class pytudes._2021.utils.binary_tree.TreeNode(val=0, left=None, right=None)

Parameters:

• val (int) –

• left (TreeNodeType) –

• right (TreeNodeType) –

pytudes._2021.utils.binary_tree._build_tree(arr, root_idx)

Recursively builds the tree rooted at arr[root_idx]

Parameters:

• arr (list[int]) –

• root_idx (int) –

Return type:

TreeNodeType

pytudes._2021.utils.binary_tree.build_tree(arr, is_1_indexed=False)

Builds a TreeNode binary tree from the values in arr

Assumes the values in arr are ordered as a binary tree

If arr is 0-indexed, internally pads arr to be 1-indexed for easier math

Args:

arr: 0- or 1-indexed array representation of a binary-tree is_1_indexed: whether or not arr is already in the expected 1-indexed representation

Returns: TreeNode root of a binary tree representing arr

Examples:

>>> assert (
...     build_tree([1,2,3], is_1_indexed=False).val ==
...     build_tree([None,1,2,3], is_1_indexed=True).val ==
...     1
... )
>>> root = build_tree([None,3,9,20,None,None,15,7], is_1_indexed=True)
>>> root.val
3
>>> root.left.val
9
>>> root.right.val
20
>>> root.right.left.val
15
>>> root.right.right.val
7

Parameters:

arr (list[int]) –

Return type:

TreeNodeType

pytudes._2021.utils.binary_tree.get_child_idx_left(index)

Args:

index: index of the binary tree element in an array representation

Returns: the left-child index of the binary tree element

Examples:

>>> arr = [None,3,9,20,None,None,15,7]
>>> arr[get_child_idx_left(1)] # 3
9
>>> arr[get_child_idx_left(3)] # 20
15

Parameters:

index (int) –

Return type:

int

pytudes._2021.utils.binary_tree.get_child_idx_right(index)

Args:

index: index of the binary tree element in an array representation

Returns: the right-child index of the binary tree element

Examples:

>>> arr = [None,3,9,20,None,None,15,7]
>>> arr[get_child_idx_right(1)] # 3
20
>>> arr[get_child_idx_right(3)] # 20
7

Parameters:

index (int) –

Return type:

int

pytudes._2021.utils.binary_tree.get_parent_idx(index)

Args:

index: index of the binary tree element in an array representation

Returns: the parent index of the binary tree element

Examples:

>>> arr = [None,3,9,20,None,None,15,7]
>>> arr[get_parent_idx(2)] # 20
3
>>> arr[get_parent_idx(len(arr)-1)] # 7
20

Parameters:

index (int) –

Return type:

int

pytudes._2021.utils.binary_tree.TreeNodeType