dsa.tree module

Module containing tree class.

class dsa.tree.Tree(root=None)

Bases: object

A binary search tree (BST) implementation. Can be treated as a plain binary tree if operations (insert, search, delete) are not used and nodes are set manually.

delete(value)

Delete a value from the binary search tree.

Parameters:

value – The value to delete.

Returns:

The root of the tree after insertion.

Raises:

ValueError – if value is not found.

delete_iterative(root, value)

Delete a value from the binary search tree (iterative version).

Parameters:

value – The value to delete.

Returns:

The root of the tree after insertion.

Raises:

ValueError – if value is not found.

delete_node(node, value)

Helper function to delete a value from the binary search tree. (Use delete() instead)

Parameters:

• value – The value to delete.

• node – The current node.

Returns:

The new subtree root after deletion.

Raises:

ValueError – if value is not found.

insert(value)

Insert a value in the binary search tree.

Parameters:

value – The value to insert.

Returns:

The root of the tree after deletion.

Raises:

ValueError – if value is already in the tree

insert_iterative(value)

Insert a value in the binary search tree (iterative implementation).

Parameters:

value – The value to insert.

Returns:

None

Raises:

ValueError – if value is already in the tree

insert_rec(root, value)

predecessor_node(node=None)

Return the predecessor node (the maximum value in a binary search tree’s left subtree).

Parameters:

node – The starting node.

Returns:

node with the lowest value in the BST None if not found

Raises:

ValueError – if value is not found.

print()

Print the values in the BST.

search(value)

Search for a value in the binary search tree.

Parameters:

value – Value to search for.

Returns:

node with matching value

Raises:

ValueError – if value is not found

successor_node(node=None)

Return the successor node (the minimum value in a binary search tree’s right subtree).

Parameters:

node – The starting node.

Returns:

node with the lowest value in the BST None if not found

Raises:

ValueError – if value is not found.

class dsa.tree.TreeNode(value, left=None, right=None)

Bases: object

A binary tree node implementation.

copy()

Return a copy of the node.

print(level=0)

Print the contents of a node.

Parameters:

level – starting level of node