Tree¶

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

• n is the number of nodes currently in the tree.

TreeNode()¶

Here are all of the public methods that can be used with TreeNode() objects:

class extra.trees.tree.TreeNode(value)¶

A tree node is the basic unit for building trees. A tree node must contain a value and this value can’t be None. Each tree node has zero or more child tree nodes. The node that has no children is called a leaf node.

__init__(value)¶

Creates a TreeNode() object which is the basic unit for building Tree() objects!!

Parameters:	value (object) – The value to be saved within the TreeNode() instance
Raises:	ValueError: – If the given item is None. TypeError: – If the given item is an Extra() object.

Examples

>>> x = TreeNode(10)
>>> x
TreeNode(10)
>>> type(x)
<class 'extra.trees.tree.TreeNode'>

You can’t initialize a TreeNode() using a None

>>> TreeNode(None)
ValueError: Can't use `None` as an element within `extra.TreeNode()`!!

__repr__()¶

Represents TreeNode() object as a string.

Returns:	A string representing the TreeNode() instance.
Return type:	str

Example

>>> x = TreeNode(10)
>>> x
TreeNode(10)

get_children()¶

Returns a list of all the children of the TreeNode() instance.

Returns:	A list of all the children of the TreeNode() instance.
Return type:	list

Example

>>> x = TreeNode(2021)
>>> y = TreeNode("hello")
>>> z = TreeNode("world")
>>> x.set_child(y)
>>> x.set_child(z)
>>> x.get_children()
[TreeNode(hello), TreeNode(world)]

get_data()¶

Returns the data stored in the TreeNode() instance.

Returns:	The object stored in the TreeNode().
Return type:	object

Example

>>> x = TreeNode(10)
>>> x.get_data()
10

is_leaf()¶

Checks if the current TreeNode() instance is a leaf node. A leaf node is a tree node that has no children.

Returns:	True if the current TreeNode() has no children and False otherwise.
Return type:	bool

Example

>>> x = TreeNode("hello")
>>> x.is_leaf()
True
>>> x.set_child(TreeNode("world"))
>>> x.is_leaf()
False

set_child(child)¶

Sets the given TreeNode() as a child for the current TreeNode().

Parameters:	child (TreeNode()) – The TreeNode() that will be a child for the current one.
Raises:	TypeError: – If the given item is not an TreeNode() object.

Example

>>> x = TreeNode("hello")
>>> x.set_child(TreeNode("world"))
>>> x.set_child(TreeNode(2021))

A child has to be a TreeNode() object:

>>> x.set_child(20)
TypeError: You can't set a child unless it's an `extra.TreeNode()`             object!!

set_children(lst)¶

Sets multiple TreeNode() instances as children for the current one.

Parameters:	lst (iterable (list, tuple, ..)) – A list of the TreeNode() instances that will be set as children to the current TreeNode().
Raises:	TypeError: – This can be raised in either of these two cases: 1. If the given object isn’t iterable. 2. If the given object has an element which isn’t a TreeNode() instance.

Example

>>> x = TreeNode("hello")
>>> x.set_children([TreeNode("world"), TreeNode(2021)])

A child has to be a TreeNode() object:

>>> x.set_children([TreeNode("world"), 2021])
TypeError: You can't set a child unless it's an `extra.TreeNode()`             object!!

Tree()¶

Here are all of the public methods that can be used with Tree() objects:

class extra.trees.tree.Tree¶

A tree is a non-linear data structure that can be defined recursively using a collection of TreeNode() instances, where each node has a list of references to the children TreeNode() instances.

__contains__(value)¶

Searches the Tree() for the given value and returns True if the value exists and False if not.

Parameters:	value (object) – The value to be searched for in the Tree() instance.
Returns:	Returns True if the value exists in the Tree() instance and False if not.
Return type:	bool

Examples

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> 100 in t
True
>>> 50 in t
False

__init__()¶

Creates an empty Tree() object!!

Example

>>> t = Tree()
>>> type(t)
<class 'extra.trees.tree.Tree'>

__iter__()¶

Iterates over the Tree() instance and returns a generator of the TreeNode() values in breadth-first manner.

Yields:	object – The value stored at each node in the Tree() instance.

Examples

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> for value in t:
...     print(value)
10
100
200
1
2
3
4
5

__len__()¶

Gets the length of the Tree() instance. Length is the number of nodes in the instance.

Returns:	The length of the Tree() instance. Length is the number of tree nodes in the instance.
Return type:	int

Examples

>>> t = Tree()
>>> len(t)
0
>>> x = TreeNode(2021)
>>> y = TreeNode("hello")
>>> z = TreeNode("world")
>>> x.set_children([y, z])
>>> t._root = x
>>> t
2021
├── hello
└── world
>>> len(t)
3

__repr__()¶

Represents the Tree() instance as a string.

Returns:	The string-representation of the Tree() instance.
Return type:	str

Example

>>> t = Tree()
>>> t
--
>>> # the following is "The Simpsons" family tree :)
>>> abraham = TreeNode('Abraham')
>>> herb = TreeNode('Herb')
>>> homer = TreeNode('Homer')
>>> abraham.set_children([herb, homer])
>>> # homer-marge children
>>> bart = TreeNode('Bart')
>>> lisa = TreeNode('Lisa')
>>> maggie = TreeNode('Maggie')
>>> homer.set_children([bart, lisa, maggie])
>>> root = TreeNode('TheSimpsons')
>>> root.set_child(abraham)
>>> t._root = root
>>> t
TheSimpsons
└─┬ Abraham
  ├── Herb
  └─┬ Homer
    ├── Bart
    ├── Lisa
    └── Maggie

clear()¶

Removes all nodes within the Tree() instance in constant time.

Example

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> t.clear()
>>> t
--
>>> t.is_empty()
True

count_leaf_nodes()¶

Counts the number of leaf nodes in the Tree() instance. Leaf nodes are the tree nodes that have no children.

Returns:	A positive integer representing the number of leaf nodes in the Tree().
Return type:	int

Example

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> t.count_leaf_nodes()
5

static from_path(path)¶

Creates a Tree() instance of the hierarchy of a given directory/path. Each file in each sub-directory will be represented as a TreeNode() instance.

Parameters:	path (str) – The path which will be the root of the returned Tree() object.
Returns:	The Tree() object representing the hierarchy of the given path.
Return type:	Tree()
Raises:	TypeError: – If the given path’s type wasn’t a string. ValueError: – If the given path doesn’t exist.

Example

>>> # this can't be reproduced and it's for the sake of explanation.
>>> Tree.from_path("example")
trees
├── script.py
├─┬ folder
│ ├── file.txt
│ ├── file2.txt
│ └── file3.txt
├── script2.py
└── script3.py

get_depth()¶

Gets the depth of the Tree() instance.

Returns:	A positive integer representing the depth of the given Tree().
Return type:	int

Example

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> t.get_depth()
0

get_height()¶

Gets the height of the Tree() instance. The tree’s height is the number of edges between the root and the furthest leaf node.

Returns:	A positive integer representing the height of the instance.
Return type:	int

Example

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> t.get_height()
2

get_nodes_per_level()¶

Retreeves all treenodes within the Tree() instance so that all treenodes in a certain level will be concatenated into a separate list.

Returns:	A nested list where the first inner-list has all the tree nodes in the first level, the second inner-list has all the tree nodes in the second level, … so on.
Return type:	list

Example

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> t.get_nodes_per_level()
[[10], [100, 200], [1, 2, 3, 4, 5]]

is_empty()¶

Checks if the Tree() instance is empty or not in constant time.

Returns:	A boolean flag showing if the Tree() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> t = Tree()
>>> t.is_empty()
True
>>> t._root = TreeNode(1)
>>> t.is_empty()
False

to_list()¶

Converts the Tree() instance to a list where values will be inserted in breadth-first manner.

Returns:	A list object containing the same elements as the Tree() instance.
Return type:	list

Example

>>> t = Tree()
>>> root = TreeNode(10)
>>> first_child = TreeNode(100)
>>> second_child = TreeNode(200)
>>> first_child.set_children([TreeNode(1), TreeNode(2), TreeNode(3)])
>>> second_child.set_children([TreeNode(4), TreeNode(5)])
>>> root.set_children([first_child, second_child])
>>> t._root = root
>>> t
10
├─┬ 100
│ ├── 1
│ ├── 2
│ └── 3
└─┬ 200
  ├── 4
  └── 5
>>> t.to_list()
[10, 100, 200, 1, 2, 3, 4, 5]