DSA module

class DSA.BSTNode(info: int)

Bases: object

BST Node class.

Available member functions include:

initialising constructor

string converter

__init__(info: int) → None

Construct new BST Node object

Args:

info: value of the node

>>> from DSA import BSTNode
>>> n = BSTNode(4)
>>> type(n)
<class 'DSA.BSTNode'>

__str__() → str

Return node value as a string for printing

Return:

str: string of the node value

>>> from DSA import BSTNode
>>> n = BSTNode(4)
>>> print(n)
4

class DSA.BinarySearchTree

Bases: object

Binary Search Tree class.

Available member functions include:

initialising constructor

insert

traverse

height

__init__() → None

Construct a new Binary Search Tree object

>>> from DSA import BinarySearchTree
>>> t = BinarySearchTree()
>>> type(t)
<class 'DSA.BinarySearchTree'>

height(root: BSTNode) → int

Calculates height of the tree

Args:

root: node to calculate height for

>>> from DSA import BinarySearchTree
>>> t = BinarySearchTree()
>>> t.insert(3)
>>> t.insert(1)
>>> t.insert(6)
>>> t.insert(4)
>>> t.insert(5)
>>> t.height(t.root)
3

insert(val: int) → None

Insert node into the tree

Args:

val: input value for the node

>>> from DSA import BinarySearchTree
>>> t = BinarySearchTree()
>>> t.insert(3)
>>> t.insert(1)
>>> t.insert(6)
>>> t.insert(4)
>>> t.insert(5)
>>> t.traverse('IN')
1 3 4 5 6 

traverse(order: str) → None

Traverses the tree

Args:

order: traversal method out of ‘PRE’, ‘IN’ and ‘POST’

>>> from DSA import BinarySearchTree
>>> t = BinarySearchTree()
>>> t.insert(3)
>>> t.insert(1)
>>> t.insert(6)
>>> t.insert(4)
>>> t.insert(5)
>>> t.traverse('IN')
1 3 4 5 6 

class DSA.DoublyLinkedList

Bases: object

Doubly Linked List class.

Available member functions include:

initialising constructor

insert

printer

reverse

__init__() → None

Construct a new Singly Linked List Node object

>>> from DSA import DoublyLinkedList
>>> l = DoublyLinkedList()
>>> type(l)
<class 'DSA.DoublyLinkedList'>

insert(data: int) → None

Insert node into the list

Args:

data: input value for the node

>>> from DSA import DoublyLinkedList
>>> l = DoublyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(3)
>>> l.printer()
[1, 2, 3]

printer(sep: str = ', ') → None

Print the list

Args:

sep: string separator

>>> from DSA import DoublyLinkedList
>>> l = DoublyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(3)
>>> l.printer()
[1, 2, 3]

reverse() → None

Reverse the list

>>> from DSA import DoublyLinkedList
>>> l = DoublyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(3)
>>> l.reverse()
>>> l.printer()
[3, 2, 1]

class DSA.DoublyLinkedListNode(data: int)

Bases: object

Doubly Linked List Node class.

Available member functions include:

initialising constructor

string converter

__init__(data: int) → None

Construct new Doubly Linked List Node object

Args:

data: value of the node

>>> from DSA import DoublyLinkedListNode
>>> n = DoublyLinkedListNode(3)
>>> n.data
3

__str__() → str

Return node value as a string for printing

Return:

str: string of the node value

>>> from DSA import DoublyLinkedListNode
>>> n = DoublyLinkedListNode(3)
>>> print(n)
3

class DSA.SinglyLinkedList

Bases: object

Singly Linked List class.

Available member functions include:

initialising constructor

insert

find

deleteVal

printer

reverse

__init__() → None

Construct a new Singly Linked List Node object

>>> from DSA import SinglyLinkedList
>>> l = SinglyLinkedList()
>>> type(l)
<class 'DSA.SinglyLinkedList'>

deleteVal(data: int) → bool

Delete value in the list

Args:

data: value to be deleted

Return:

bool: True/False

>>> from DSA import SinglyLinkedList
>>> l = SinglyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(4)
>>> l.insert(3)
>>> print(l.deleteVal(2))
True

find(data: int) → SinglyLinkedListNode

Find value in the list

Args:

data: value to be found

Return:

SinglyLinkedListNode: node if found

None: if not found

>>> from DSA import SinglyLinkedList
>>> l = SinglyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(4)
>>> l.insert(3)
>>> print(l.find(4))
2

insert(data: int) → None

Insert node into the list

Args:

data: input value for the node

>>> from DSA import SinglyLinkedList
>>> l = SinglyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(3)
>>> l.printer()
[1, 2, 3]

printer(sep: str = ', ') → None

Print the list

Args:

sep: string separator

>>> from DSA import SinglyLinkedList
>>> l = SinglyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(3)
>>> l.printer()
[1, 2, 3]

reverse() → None

Reverse the list

>>> from DSA import SinglyLinkedList
>>> l = SinglyLinkedList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(3)
>>> l.reverse()
>>> l.printer()
[3, 2, 1]

class DSA.SinglyLinkedListNode(data: int)

Bases: object

Singly Linked List Node class.

Available member functions include:

initialising constructor

string converter

__init__(data: int) → None

Construct a new Singly Linked List Node object

Args:

data: input value for the node

>>> from DSA import SinglyLinkedListNode
>>> n = SinglyLinkedListNode(2)
>>> n.data
2

__str__() → str

Return node value as a string for printing

Returns:

str: string of the node value

>>> from DSA import SinglyLinkedListNode
>>> n = SinglyLinkedListNode(2)
>>> print(n)
2

class DSA.Trie

Bases: object

Trie class.

Available member functions include:

initialising constructor

find

insert

checkPrefix

countPrefix

__init__() → None

Construct a new Trie object

>>> from DSA import Trie
>>> t = Trie()
>>> type(t)
<class 'DSA.Trie'>

checkPrefix(s: str) → bool

Check if string is a prefix

Args:

s: string to check

Return:

bool: True/False

>>> from DSA import Trie
>>> t = Trie()
>>> t.insert('abcd')
>>> t.insert('ace')
>>> t.insert('about')
>>> t.checkPrefix('ab')
True

countPrefix(s: str) → int

Count strings who have some prefix

Args:

s: string to check prefix

>>> from DSA import Trie
>>> t = Trie()
>>> t.insert('abcd')
>>> t.insert('ace')
>>> t.insert('about')
>>> t.countPrefix('ab')
2

find(root: dict, c: str) → bool

Find a char in a Trie

Args:

root: Trie to search

c: character to find

Return:

bool: True/False

>>> from DSA import Trie
>>> t = Trie()
>>> t.insert('abcd')
>>> t.insert('ace')
>>> t.insert('about')
>>> t.find(t.T['a']['b'],'o')
True

insert(s: str) → None

Insert string into the Trie

Args:

s: string to insert

>>> from DSA import Trie
>>> t = Trie()
>>> t.insert('abcd')
>>> t.insert('ace')
>>> t.insert('about')
>>> t.find(t.T['a']['b'],'o')
True

DSA.merge(list1: SinglyLinkedList, list2: SinglyLinkedList) → SinglyLinkedList

Merge two sorted linked lists

Args:

list1: first list

list2: second list

Return:

SinglyLinkedList: merged list

>>> from DSA import SinglyLinkedList, merge
>>> L1 = SinglyLinkedList()
>>> L1.insert(2)
>>> L1.insert(4)
>>> L1.insert(7)
>>> L2 = SinglyLinkedList()
>>> L2.insert(1)
>>> L2.insert(4)
>>> L2.insert(5)
>>> merge(L1,L2).printer()
[1, 2, 4, 4, 5, 7]